递归函数思路分析

冷不防 2023-09-30 18:33 5阅读 0赞

> 1、递归，实际上是简化嵌套for循环的一种精简算法，所以递归函数就是在函数内部自己调用自己，并**不断改变递归参数**的过程。
> 
> 2、**递归函数的出口通常是用return或if-else语句**来避免再调用自己。

> 下面的代码分别用递归和for循环实现的阶乘：
> 
>     ## 递归实现阶乘
>     def factorial(n):
>       if n == 1:
>         return 1
>       else:
>         return n * factorial(n-1)
>     print(factorial(5)) # 120
>     
>     ## for循环实现阶乘
>     def factorial(n):
>       res = 1
>       for i in range(n, 0, -1):
>         res *= i
>       return res
>     print(factorial(5)) # 120
> 
> 对比发现：
> 
> **1、****第一次阶乘递归的参数（n为5）相当于 for循环中的循环变量的初始值range(n, 0, -1)中的start值n（=5）。**
> 
> **2、****递归函数中的factorial(n-1)的（n-1）相当于 for循环中的循环变量的改变步长range(n, 0, -1)中的-1。**
> 
> **3、****递归结束的条件是n==1 相当于 for循环中的循环变量的结束值range(n, 0, -1)中的stop值0。**
> 
> 补充：Python中的range(start, stop, step)函数的范围是\[start, stop)。

> Python中递归最大调用深度默认为1000
> 
>     import sys
>     print(sys.getrecursionlimit()) # 1000
>     sys.setrecursionlimit(2000)
>     print(sys.getrecursionlimit()) # 2000

> ### 写递归函数时的思路： ###
> 
> 1、利用IDE的**调试功能**进行单步调试，可以直观观察递归调用的全过程。
> 
> 2、先用简单的测试用例测试递归函数，在**逐级增大递归调用的深度**，一般递归深度到3~5层就可以验证递归函数是否满足要求。
> 
> #### 3、**由于递归调用的过程是** **不断改变递归参数** **的过程，也就是说，在递归函数内部必定有改变递归参数的语句，那么递归函数的自身调用一定出现在改变递归参数的那条语句之后，这个结论非常有助于引导我们编写我们的递归函数。** ####