## 递归示例 1


```python
# 计算 1 + 2 + ... + n 的和
def calc_sum(n):
    if n == 0:
        return 0
    return n + calc_sum(n - 1)
```


```python
print(calc_sum(10))
```

    55


## 递归练习 1


```python
# 计算 1 * 2 * ... * n 的积
def calc_product(n):
    return 0
```


```python
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}
$$



```python
def fibonacci(n):
    return 0
```

## 算法实例 1

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


```python
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 就是排列好的数组了

```


```python
# 这是快速排序的算法。如果感兴趣，可以看一下下面的视频：
# 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) 

```

我们运行一下两种算法：


```python
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 秒


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

c3cefbf3146707bc450383687da14b6d1aeca762
ipynb
Jupyter Notebook
m5-101/content/algorithms-practice/algorithms-practice.ipynb
PaulCCCCCCH/m5-101
81201b00cd81c1747ea0cd5f042a09eda02d6d1c
MIT
2021-03-25T13:15:38.000Z
2021-11-10T12:29:19.000Z
m5-101/content/algorithms-practice/algorithms-practice.ipynb
PaulCCCCCCH/m5-101
81201b00cd81c1747ea0cd5f042a09eda02d6d1c
MIT
m5-101/content/algorithms-practice/algorithms-practice.ipynb
PaulCCCCCCH/m5-101
81201b00cd81c1747ea0cd5f042a09eda02d6d1c
MIT
2021-03-25T13:18:10.000Z
2021-04-08T13:44:48.000Z
Qwen/Qwen-72B
1. YES
2. YES