假设你在祖母的阁楼中翻箱倒柜，发现了一个上锁的神秘手提箱。

祖母告诉你，钥匙很可能在下面这个盒子里。

这个盒子里有盒子，而盒子里的盒子又有盒子。钥匙就在某个盒子中。为找到钥匙，你将使用什么算法？先想想这个问题，再接着往下看。

下面是一种方法。

• 创建一个要查找的盒子堆。
• 从盒子堆取出一个盒子，在里面找
• 如果找到的是盒子，就将其加入盒子堆中，以便以后再查找。
• 如果找到钥匙，则大功告成！
• 回到第二步。

下面是另一种方法。

• 检查盒子中的每样东西。
• 如果是盒子，就回到第一步。
• 如果是钥匙，就大功告成！

在你看来，哪种方法更容易呢？第一种方法使用的是while循环：只要盒子堆不空，就从中取一个盒子，并在其中仔细查找。

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 "found the key!"

第二种方法使用递归——函数调用自己，这种方法的伪代码如下。

def look_for_key(box):
    for item in box:
        if item.is_a_box():
            look_for_key(item)
        elif item.is_a_key():
            print "found the key!"

这两种方法的作用相同，但在我看来，第二种方法更清晰。递归只是让解决方案更清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。我很喜欢Leigh Caldwell在Stack Overflow上说的一句话：“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。”

参见：http://stackoverflow.com/a/72694/139117

很多算法都使用了递归，因此理解这种概念很重要。