深入理解递归

递归是很多算法都使用的一种编程方法。

递归的思想

以此类推是递归的基本思想。

具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时,因为解决大问题的方法和解决小问题的方法往往是同一个方法,所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件,这样就不会产生无限递归的情况了。

递归的两个条件

编写递归函数时,必须告诉它何时停止递归。正因为如此,每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则指的是函数不再调用自己,从而避免形成无限循环。

1
2
3
4
5
6
def countdown(i):
print(i)
if i <= 0:
return
else:
countdown(i-1)

其中 i <= 0 就是基线条件,而 else 是递归条件。

递归的过程

在求解6的阶乘时,递归过程如下所示。

我们会惊奇的发现这个过程和栈的工作原理一致对,递归调用就是通过栈这种数据结构完成的。整个过程实际上就是一个栈的入栈和出栈问题。然而我们并不需要关心这个栈的实现,这个过程是由系统来完成的。

其中递归中的“递”就是入栈,递进;“归”就是出栈,回归

下面是其Python实现:

1
2
3
4
5
6
7
def fib(self,n):
if n == 1:
return 1
elif n == 2:
return 1
else:
return fib(n-1)+fib(n-2)

参考

赞赏一杯咖啡
0%