递归函数

首先说一下递归函数的核心思想：

每一次递归，整体问题都要比原来减小，并且递归到一定层次时，要能直接给出结果！

接下来跟大家举个例子

求和

普通方法实现

def sum_number(n):

    total= 0

    for iin range(1,n+1):

        total+= i

return total

如果用递归的方式实现，代码将会很简介

def sum_number(n):

    if n == 0:

        return 0

    return n + sum_number(n-1)

函数调用

count= sum_number(100)

print(count)

其实所有的递归函数都可以写成循环的方式，但是循环的逻辑不如递归清晰

接下来在大家写一个例子

阶乘

def factorial(n):

    if n == 1:

        return 1

    else:

        return n * factorial(n-1)

factorial(5)

接下来分析一下代码是如何执行的

factorial(5)                                    # 第 1 次调用使用 5

5 * factorial(4)                              # 第 2 次调用使用 4

5 * (4 * factorial(3))                      # 第 3 次调用使用 3

5 * (4 * (3 * factorial(2)))               # 第 4 次调用使用 2

5 * (4 * (3 * (2 * factorial(1))))       # 第 5 次调用使用 1

5 * (4 * (3 * (2 * 1)))                      # 从第 5 次调用返回

5 * (4 * (3 * 2))                             # 从第 4 次调用返回

5 * (4 * 6)                                     # 从第 3次调用返回

5 * 24                                          # 从第 2 次调用返回

120                                              # 从第 1 次调用返回

使用递归函数需要注意防止递归深度溢出，在Python中，通常情况下，这个深度是1000层，超过将抛出异常。在计算机中，函数递归调用是通过栈（stack）这种数据结构实现的，每当进入一个递归时，栈就会加一层，每当函数返回一次，栈就会减一层。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。