递归与栈

递归

递归是很多算法都使用的一种编程方法，具体的表现在于自己调用自己。

举例：

从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？"从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？'从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！故事是什么呢？…...

买的礼品,包装盒子里有第二层包装盒，第二层包装盒里有第三层包装盒，第三层包装盒里有包装纸.....

如上的故事翻译成伪代码如下：

def gu_shi():
  print('从前有座山，山里有座庙，庙里有个老和尚，正在给小和尚讲故事呢！')
  gu_shi()

def bao_zhuang():
  print('有包装，继续拆')
  bao_zhuang()

基线条件和递归条件

由于递归函数调用自己，因此编写这样的函数时很容出错，进而导致无线循环。例如，假设你要编写一个倒计时的函数

5...4...3...2...1

为此，我们可以用递归的方式编写，如下所示：

def count_down(i):
  print(i)
  count_donw(i-1)

如果运行上面代码，那么就会进入死循环，直到内存益处或者强制退出(Ctrl+C)

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

修改上面的代码如下：

def count_down(i):
  print(i)
  if i<=1:
    return
  else:
      count_donw(i-1)

调用栈

调用栈（call stack）不仅对编程来说很重要，使用递归也必须理解这个概念

举例：

我们买个来的薯愿(盒装)，假如在包装时一片一片的装盒（压入，在最上的面的那片上添加新的薯片）。在我们吃打个包装时，我们上面撕开一个口，一片片取出来（弹出，获取最上面那片薯片并吃掉）

递归调用栈

递归函数也使用调用栈

举例：

我们写一个5的阶乘。定义：5！=5 4 3 2 1 。同理，3！=3 2 1

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

小结

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