GoFaster

V1

2022/08/09阅读:28主题:默认主题

python递归函数

从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事!故事是什么呢?『从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事!故事是什么呢?』……

上面这段耳熟能详的童谣,便是基础的递归,在一次一次循环中调用自己本身。

尾递归基于函数的尾调用, 
每一级调用直接返回函数的返回值更新调用栈,
而不用创建新的调用栈, 
类似迭代的实现, 
时间和空间上均优化了一般递归!
def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

递归的一个视觉效果呈现 - 捧着画框的蒙娜丽莎:

递归(Recursion),在数学与计算机科学中,是指在函数的定义中使用函数自身的方法。

在使用递归时,需要注意以下几点:

  1. 递归就是在过程或函数里调用自身

  2. 必须有一个明确的递归结束条件,称为递归出口。

典型的算法 大多数学过数学、计算机科学或者读过编程相关书籍的人,想必都会遇到阶乘:

n! = 1 × 2 × 3 × … × n

也可以用递归方式定义:

n! = (n-1)! × n

其中,n >= 1,并且 0! = 1。

由于简单、清晰,因此其常被用作递归的示例。 除了阶乘以外,还有很多算法可以使用递归来处理,例如:斐波那契数列汉诺塔等。

如下函数实例为基础迭代

开始时,result 为 1,进入 for 循环,对之前的结果累积乘以 i,直至 n。

>>> def factorial(n):
      result = 1
      for i in range(2, n+1):
        result *= i
      return result
 
 
>>> factorial(1)
1
>>> 
>>> factorial(5)
120
>>> 
>>> factorial(10)
3628800

那么递归如何实现?

>>> def factorial(n):
...     if n == 1:
...         return 1
...     else:
...         return n * factorial(n - 1)
... 
>>> 
>>> factorial(1)
1
>>> 
>>> factorial(5)
120
>>> 
>>> factorial(10)
3628800

当使用正整数调用 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 次调用返回

递归的优缺点: 从 编程之美 的角度来看,引用一句伟大的计算机编程名言:

To iterate is human,to recurse divine.
迭代者为人,递归者为神。
– L. Peter Deutsch

优点:

递归使代码看起来更加整洁、优雅

可以用递归将复杂任务分解成更简单的子问题

使用递归比使用一些嵌套迭代更容易

缺点:

递归的逻辑很难调试、跟进

递归调用的代价高昂(效率低),因为占用了大量的内存和时间。

分类:

后端

标签:

Python

作者介绍

GoFaster
V1