递归示例 1

In [18]:
# 计算 1 + 2 + ... + n 的和
def calc_sum(n):
    if n == 0:
        return 0
    return n + calc_sum(n - 1)
In [19]:
print(calc_sum(10))

55

递归练习 1

In [20]:
# 计算 1 * 2 * ... * n 的积
def calc_product(n):
    return 0
In [21]:
print(calc_product(5)) # 需要输出 120

0

递归练习 2

请使用递归计算斐波那契数列的第 n 项。 如果用递归的话，你会发现和数学公式非常像，即 $$ \begin{equation} f(n)= \begin{cases} f(n-1)+f(n-2), & \text{if}\ n \gt 2\\ 1, & \text{if}\ n = 1 \text{ or } n = 2 \end{cases} \end{equation} $$

In [22]:
def fibonacci(n):
    return 0

算法实例 1

我们比较两种排序算法，sort_numbers_slow 和 sort_numbers_fast。它们的定义如下。

In [23]:
def sort_numbers_slow(numbers):
    result = []     # 这里记录排列好的序列
    while numbers:  # 一直循环，直到 numbers 为空
        curr_max = -float('inf')    # 记录当前最大的数，因为还没开始，所以是负无穷大
        curr_max_idx = 0            # 记录当前最大的数在第几个
        for idx in range(len(numbers)):  
            if numbers[idx] > curr_max:
                curr_max = numbers[idx] 
                curr_max_idx = idx

        numbers.pop(curr_max_idx)   # 把 numbers 里面最大的那个数扔掉
        result.append(curr_max)     # 把这个最大的数放到 result 数组里面

    return result                   # 返回的 result 就是排列好的数组了
In [24]:
# 这是快速排序的算法。如果感兴趣，可以看一下下面的视频：
# https://www.bilibili.com/video/BV1at411T75o?from=search&seid=14008345895727111022
def sort_numbers_fast(numbers):
    
    def partition(arr,low,high): 
        i = low - 1
        pivot = arr[high]     
        for j in range(low , high): 
            if arr[j] <= pivot: 
                i = i+1 
                arr[i],arr[j] = arr[j],arr[i] 
        arr[i + 1], arr[high] = arr[high], arr[i + 1] 
        return (i + 1) 

    def quick_sort(arr, low, high): 
        if low < high: 

            pi = partition(arr, low, high) 

            quick_sort(arr, low, pi - 1) 
            quick_sort(arr, pi + 1, high) 
    
    quick_sort(numbers, 0, len(numbers) - 1)

我们运行一下两种算法：

In [25]:
import random
import time

# 创建一个随机打乱了的数组
numbers = [random.randint(0, 20000) for _ in range(20000)]

# 开始计时
start = time.time()
print("开始运行 sort_numbers_slow")
# 开始用比较慢的算法排序
sort_numbers_slow(list(numbers))
# 停止计时
end = time.time()
print("sort_numbers_slow 运行完成，耗时 {} 秒".format(end-start))

# 开始计时
start = time.time()
print("开始运行 sort_numbers_fast")
# 开始用更快速的算法排序
sort_numbers_fast(list(numbers))
# 停止计时
end = time.time()
print("sort_numbers_fast 运行完成，耗时 {} 秒".format(end-start))

开始运行 sort_numbers_slow
sort_numbers_slow 运行完成，耗时 6.283639192581177 秒
开始运行 sort_numbers_fast
sort_numbers_fast 运行完成，耗时 0.031037330627441406 秒

可以看到，两种算法的效率差别非常明显地别。
虽然现在我们不要求大家掌握任何算法，但是希望各位在用程序解决问题的时候，要有算法效率的意识。