算法小专栏：递归与尾递归
本篇将介绍递归与尾递归的相关内容。
一、什么是“递归”？
递归是一种优雅的解决问题的方法。
看一段最简单的递归例子：
Fibonacci数（斐波那契数）：我们都知道Fibonacci数的递推公式为：
- F(0)=F(1)=1，
- 当n>=2时，F(n)=F(n-1)+F(n-2)
用Python写，就是这样：
def Fibonacci(n):
if(n>=2):
return Fibonacci(n - 1) + Fibonacci(n - 2)
elif (n==0 or n==1):
return 1
else:
return -1
print Fibonacci(20)
递归，简单来说，就是在运行的过程中调用自己。
递归能帮我们处理一些复杂的算法问题，但绝不能滥用递归。
在程序设计角度，循环的性能要好于递归。
从开发角度，使用递归，逻辑上更容易被理解。
所以，要分场合使用递归，用好递归。
二、基线条件和递归条件
一个递归的实现一定少不了基线条件和递归条件。
那么，什么是“基线条件”？什么又是“递归条件”呢？
| 名称 | 描述 |
|---|---|
| 递归条件 | 函数调用自己的条件。 |
| 基线条件 | 函数不再调用自己的条件，从而避免形成无限循环。 |
拿上面Fibonacci的例子来说，
def Fibonacci(n):
if(n>=2):
return Fibonacci(n - 1) + Fibonacci(n - 2)
elif (n==0 or n==1):
return 1
else:
return -1
- 递归条件：就是
if(n>=2)。 - 基线条件：就是
elif (n==0 or n==1)。
PS：在python中，
else if的语法是elif。
三、栈
本节涉及到了内存方面的知识——调用栈（call stack）。
栈是一种简单的数据结构，当我们调用方法时，系统会执行“压栈”操作；当我们调用完方法时，系统会执行“出栈”操作。
简单来说，
- 函数调用 就意味着 => 申请栈帧，函数入栈。
- 函数返回 就意味着 => 推出栈帧，函数出栈。
PS：不过还有一种特殊的情况：叫做尾调用优化（其本质是复用栈帧，即函数调用时，不再申请新栈帧，而是复用旧的栈帧。），在下文
3.3节会重点讲解。
3.1 调用栈
我们来看这样一段代码：
def func1(param1):
func2(param1)
func3(param1)
def func2(param2):
print param2
def func3(param3):
print param3
func1(647)
解析：定义了三个函数，分别是func1、func2、func3。其中传入的参数名为param1、param2、param3。
而在内存中，会做如下操作：
3.2 递归调用栈
递归函数也会使用调用栈，我们称之为“递归调用栈”。
下面，请看这个例子：
def factorial(x):
if x == 1:
return 1
else:
return x * factorial(x-1)
print factorial(3)
解析：这是一个求阶乘的递归函数。传入参数x，得出xx-1...1的值（x>=1）。
而每一次递归，都会申请一个栈帧，这种栈帧就叫做递归调用栈。
图解如下：
3.3 尾递归
尾递归是一种高级递归方式，它可以不断的复用旧栈帧，已达到最大的内存优化。
注意：不是所有语言都支持尾递归优化（尾调用优化）。
JavaScript、Objective-C、Java、C++等支持尾递归优化，而Python本身是不支持尾递归优化的。
（关于iOS中OC的尾调用优化可以看这篇：iOS objc_msgSend尾调用优化机制详解）
Q1：什么是尾递归？什么又是尾调用？
尾递归：在函数最后一步，仅仅返回调用了自身。（注意仅仅两字）
尾调用：在函数最后一步，仅仅返回了一个函数。（注意仅仅两字）
所以，尾递归实际上是属于尾调用的一种特殊情形。
Q2：举个尾递归的例子？
int fun(int x) {
if (x > 0)
return fun(x-1);
else
return 1;
}
在函数的最后一步，仅仅return了本身的函数。符合尾递归。
Q3：尾递归究竟做了什么优化？
两张对比图一目了然：
- 非尾调用：
- 是尾调用：
Q4：尾递归的本质是什么？
答：栈帧的重复利用。
