【算法图解】递归和栈

递归

如果有一个盒子，盒子里有盒子，盒子里的盒子也有盒子，那么，怎样在一堆盒子里找出钥匙呢？

方法一

1. 创建一个要找的盒子堆。
2. 从盒子里找出一个盒子，打开。
3. 如果是盒子，就放入盒子堆，以后再查找。
4. 如果是钥匙，结束返回。
5. 回到第二步。

def look_for_key(main_box):
    pile = main_box.make_a_pile_to_look_through()
    while pile is not empty:
        box = pile.grab_a_box()
        for item in box:
            if item.is_a_box():
                pile.append(item)
            elif item.is_a_key():
                print "find the key!"

方法二

1. 检查盒子里面东西。
2. 如果是盒子，返回第一步。
3. 如果是钥匙，结束返回。

def look_for_key(box):
    for item in box:
        if item.is_a_box(): #递归条件
            look_for_key(item)
        elif item.is_a_key(): #基线条件
            print "find the key!"

第二种方法就使用了递归，自己调用自己。

栈

一个简单函数：

def greet(name):
	print "hello," + name + "!"
	greet2(name)
	print "greeting ready to say bye..."
	bye()

这个函数调用了两个函数，两个函数代码如下：

def greeet2(name):
	print "how are you," + name + "?"
def bye():
	print "ok bye!"

在内存中，这个函数运行过程如下：

1. greet()被压入栈底部。
2. greet2()被压入greet()上方。
3. 打印出greet2()结果。
4. 在栈中弹出greet2()。
5. bye()被压入greet()上方。
6. 打印出bye()结果。
7. greet()返回。

这个栈用于存储多个函数的变量，被称为调用栈。所有函数调用都进入调用栈。

递归调用栈

给定函数factorial(5)写做5!=5*4*3*2*1，那么：

def fact(x):
	if x == 1:
		return 1
	else:
		return x*fact(x-1)

fact(3)的调用栈变化如下：

1. 搭积木，最下层放入x=3，其上依次为x=2，x=1。
2. x=1满足结束条件，返回1，并弹出x=1的栈。
3. 返回2*1，弹出x=2的栈。
4. 返回3*2，结束程序。

栈使用理解方便，但是占用内存大。栈太高时，可以转用循环。