星尘

图解算法3 - 递归、栈

发表于 更新于 分类于

递归

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。

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

栈

1
2
3
4
5
6
7
8
9
10
11
def greet(name):
	print "hello, " + name + "!"
	greet2(name)
	print "getting ready to say bye..."
	bye()

def greet2(name):
	print "how are you, " + name + "?"

def bye():
	print "ok bye!"

假设你调用greet(“maggie”)，计算机将首先为该函数调用分配一块内存。变量name的值变为maggie，这需要存储到内存中，每当你调用函数时，计算机都像这样将函数调用涉及的所有变量的值存储到内存中。接下来，你打印hello, maggie!，再调用greet2(“maggie”)。同样，计算机也为这个函数调用分配一块内存。其中第二个内存块位于第一个内存块上面【greet2所在的内存块在greet内存块的上面】。你打印how are you, maggie?，然后从函数调用返回。此时，栈顶的内存块被弹出【greet2所在的内存块被弹出】。这时greet函数处于什么状态呢？
函数greet只执行了一部分，调用另一个函数时，当前函数暂停并处于未完成状态。该函数的所有变量的值都还在内存中。执行完函数greet2后，你回到函数greet，并从离开的地方开始接着往下执行：首先打印getting ready to say bye…，再调用函数bye。重复上面的操作，在栈顶添加了函数bye的内存块。然后，你打印ok bye!，并从这个函数返回。最后又回到了函数greet。由于没有别的事情要做，你就从函数greet返回。这个栈用于存储多个函数的变量，被称为调用栈。

使用栈虽然很方便，但是也要付出代价：存储详尽的信息可能占用大量的内存。每个函数调用都要占用一定的内存，如果栈很高，就意味着计算机存储了大量函数调用的信息。在这种情况下，你有两种选择：重新编写代码，转而使用循环或者使用使用尾递归。

总结

1
2
3
4
5
递归指的是调用自己的函数。
每个递归函数都有两个条件：基线条件和递归条件。
栈有两种操作：压入和弹出。
所有函数调用都进入调用栈。
调用栈可能很长，这将占用大量的内存。