递归
在我看来,递归就类似俄罗斯套娃,一次次重复去执行相同的操作,最后得出结果的过程。
很多递归的操作都可以使用循环来替代。递归并没有带来算法性能上的优势,甚至更差,但是使用递归可能让你的程序更易理解。所以理解递归这种概念很重要。
基线条件和递归条件
由于递归函数调用自己,很容易导致无线循环。比如,你需要一个倒数的函数:
def countdown(i):
print(i)
countdown(i - 1)
countdown(3)
如果运行上述代码,这个函数就会不停的运行。
编写递归函数式,必须告诉它何时停止递归,
每个递归函数都有两部分:基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己,而基线条件则 指的是函数不再调用自己,从而避免形成无限循环。
好了,我们尝试为上面的代码增加基线条件:
def countdown(i):
print(i)
if i <= 0: # 基线条件
return
else: # 递归条件
countdown(i - 1)
countdown(3)
# 3 2 1 0 程序停止
栈
调用栈不仅对于编程来说很重要,使用递归是也必须裂解这个概念。计算机在内部使用被称为调用栈的栈。
我们简单看一个例子:
# 忽略 print 这个函数带来的影响
# 开始执行函数 greet ,此时内存中开辟一块空间 greet 进入栈中
def greet(name):
# 在 greet 的内存中,添加变量name
print "hello, " + name + "!"
# 开始执行 greet2 ,此时内存中开辟空间 greet2,greet2 入栈
# greet <-- greet2 类似这种链式结构
greet2(name)
# greet2 执行完毕,出栈
# greet
print "getting ready to say bye..."
# 开始执行bye ,此时内存中开辟空间 bye,bye 入栈
# greet <-- bye
bye()
# bye 执行完毕,出栈
# greet
# 最后greet执行完毕,出栈
栈的执行逻辑就是:先进后出原则。
递归调用栈
递归调用中,存储详尽的信息可能占用大量的内存。这回付出很大的代价。如果占用过高,你需要使用循环去代替递归,或者使用尾递归优化,前提是你的语言支持尾递归优化。
小结
- 递归指的是调用自己的函数。
- 每个递归函数都有两个条件:基线条件和递归条件。
- 栈有两种操作:压入和弹出。
- 所有函数调用都进入调用栈。
- 调用栈可能很长,这将占用大量的内存