算法图解3/11

3 递归

3.1 递归与循环

递归需要调用函数本身，只要未达基线条件，持续执行函数本身，达到基线条件则按条件返回结果；
循环，文字解释起来跟递归很像，只要满足条件，继续重复操作，类似于while （i ^= 100 ） i++。

这段解释不满意，图示可能更好，以后补充。

递归性能上并无优势，但可能显示的更清晰。

“如果使用循环，程序的性能可能更高；如果使用递归，程序可能更容易理解。如何选择要看什么对你来说更重要。” (参见http://stackoverflow.com/a/72694/139117）

3.2 基线条件和递归条件

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

image.png

3.3 栈

栈是一种简单的数据结构，类似于一叠待办事项便条，一个重要的特点是：只对最上面的便条进行操作、且操作只有两个：增加一个待办事项在最上面，或者取出一个——压入（插入）和弹出（删除并读取）。

调用栈

计算机在内部使用被称为调用栈的栈。递归函数也使用调用栈。

简单来说，递归函数每次操作（直到基线条件）都会在栈上面增加一个“元素”——存储该次需要的操作，到基线条件时，为该栈的最顶部，开始返回结果，该栈弹出（删除并读取结果值），计算上一步存的操作，继续返回。
图示可能更清晰。

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

递归调用栈

小结

*递归指的是调用自己的函数
*每个递归函数都有两个条件：基线条件和递归条件
*栈有两种操作：压入和弹出
*所有函数调用都进入调用栈
*调用栈可能很长，这将占用大量的内存——一旦循环不止，就是栈溢出了？