Recursion - 递归

递归

在家里找到一个铁盒子，但是你不知道钥匙在哪里。祖母告诉你：钥匙在一个大盒子里，这个大盒子里都是盒子，盒子里面还是盒子，钥匙就在某个盒子中。下面有两种方法可以找出钥匙。

• 第一种： (1) 创建一个要查找的盒子堆 (2) 从盒子堆取出一个盒子，在里面找 (3) 如果找到的是盒子，就将其加入盒子堆中，以便之后再查找 (4) 如果找到的是钥匙，则大功告成 (5) 回到第二步

第一种方法使用的是 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!")

• 第二种： (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("found the key!") 

函数调用自己本身的方法称为递归。

• 两种方法对比： 以上两种方法的作用相同，但是第二种更为清晰。而第一种的while循环方法在某些情况下，性能上会更好。第二种只是让方法更清晰，并没有性能上的优势。就像下图中的回答，循环可能会带来性能上的提升，递归会给程序员带来提升(更容易理解)，使用哪种，取决于哪个对于你来说更重要。

基线条件和递归条件

由于递归函数调用自己，因此写代码的时候很可能会出错，让程序陷入死循环。例如，下面的倒计时函数，运行的话会没完没了：

def countdown(i):
    print(i)
    countdown(i-1)

所以编写递归函数的时候，必须定义好递归的条件。每个递归函数都包含两部分：基线条件（base case）和递归条件（recursive case）。递归条件指的是函数调用自己，而基线条件指的是函数不再调用自己。 使用基线条件和递归条件修改上面代码:

def countdown(i):
    print(i)
    if i <= 1:  # base case 
        return
    else:      # recursive case
        countdown(i-1)