递归

Posted on | In

寻找盒子中的钥匙

while方法

  1. 创建一个要查找的盒子堆
  2. 从盒子堆里取出一个盒子，在里面找
  3. 如果找到的是盒子，就将其加入盒子堆中，以后再查找
  4. 如果找到钥匙，则大功告成
  5. 返回第二步
1
2
3
4
5
6
7
8
9
def look_for_key(box):
  pile = main_box.make_a_pile_to_look()
  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_key():
        print "found the key!"

递归方法

  1. 检查盒子中每一样东西
  2. 如果是盒子，就回到第一步
  3. 如果是钥匙，则大功告成
1
2
3
4
5
6
def look_for_key(box):
  for item in box:
    if item.is_a_box():
      look_for_key(item)
    elif item.is_key():
      print "found the key!"

如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解
每一个递归函数都有两个部分：基线条件（函数不在调用自己）和递归条件（函数调用自己）

栈

计算机在内部使用被称为 调用栈 的栈。

1
2
3
4
5
6
7
8
9
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 "bye"

当运行函数greet(name)的时候需要调用另外两个函数。

函数的调用过程

当你调用greet(“chris”)的时候，计算机首先为函数调用分配一块内存，变量信息会存在内存中。首先会打印hello world，然后调用greet2(“chris”).同样的greet2(“chris”)函数也会被分配一个内存块。计算机会使用一个栈来表示这些内存块，其中第二个内存块在第一个内存块上面。当第二个内存块的函数执行完毕，调用返回时，第二个内存块会从栈内被弹出。此时继续执行第一个内存块的内容() 当调用另一个函数的时候，当前函数暂定并处于未完成状态 )。此时第一个内存块执行bye()函数，和之前类似，分配内存块并执行，执行完后被弹出栈。一直到栈中没有任何内存块可以执行为止。
这个栈存储了多个函数的变量，被称为调用栈。

递归函数栈

1
2
3
4
5
def fact(x):
  if x == 1:
    return 1
  else:
    x = x*fact(x-1)

使用栈虽然方便，但是也要符出代价：存储详尽的信息可能占用大量的内存。这种情况下两种选择：1.重新编码，使用循环 2.使用尾递归