递归

在我看来，递归就类似俄罗斯套娃，一次次重复去执行相同的操作，最后得出结果的过程。

很多递归的操作都可以使用循环来替代。递归并没有带来算法性能上的优势，甚至更差，但是使用递归可能让你的程序更易理解。所以理解递归这种概念很重要。

基线条件和递归条件

由于递归函数调用自己，很容易导致无线循环。比如，你需要一个倒数的函数：

def countdown(i):  print(i)  countdown(i - 1)countdown(3)复制代码

如果运行上述代码，这个函数就会不停的运行。

编写递归函数式，必须告诉它何时停止递归，

每个递归函数都有两部分：基线条件(base case)和递归条件(recursive case)。递归条件指的是函数调用自己，而基线条件则 指的是函数不再调用自己，从而避免形成无限循环。

好了，我们尝试为上面的代码增加基线条件：

def countdown(i):  print(i)  if i <= 0: # 基线条件    return  else: # 递归条件    countdown(i - 1)countdown(3)# 3 2 1 0 程序停止复制代码

栈

调用栈不仅对于编程来说很重要，使用递归是也必须裂解这个概念。计算机在内部使用被称为调用栈的栈。

我们简单看一个例子：

# 忽略 print 这个函数带来的影响# 开始执行函数 greet ，此时内存中开辟一块空间 greet 进入栈中def greet(name):  # 在 greet 的内存中，添加变量name  print "hello, " + name + "!"  # 开始执行 greet2 ，此时内存中开辟空间 greet2，greet2 入栈  # greet <-- greet2 类似这种链式结构  greet2(name)  # greet2 执行完毕，出栈  # greet  print "getting ready to say bye..."   # 开始执行bye ，此时内存中开辟空间 bye，bye 入栈  # greet <-- bye  bye()  # bye 执行完毕，出栈  # greet# 最后greet执行完毕，出栈复制代码

栈的执行逻辑就是：先进后出原则。

递归调用栈

递归调用中，存储详尽的信息可能占用大量的内存。这回付出很大的代价。如果占用过高，你需要使用循环去代替递归，或者使用尾递归优化，前提是你的语言支持尾递归优化。

小结

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