1.7　从前有座山，山里有座庙：递归之法

递归调用是函数内部调用自身的过程。递归必须要有结束条件，否则会进入无限递归状态，永远无法结束。

1. 递归函数

训练1-32：输入n个整数，倒序输出所有整数。

2. 递归原理

递归包括递推和回归。递推指将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始时的原问题，返回原问题的解。

阶乘是典型的递归调用问题，5的阶乘递推、回归过程如下图所示。

训练1-33：输入一个整数n，输出n的阶乘。

注意：在递归算法中，每一次递推都需要一个栈空间来保存调用记录，因此在计算空间复杂度时需要计算递归栈的辅助空间。

上图中的递推、回归过程是我们从逻辑思维上推理并用图形象表达出来的，但其在计算机内部是怎样处理的呢？计算机使用了一种被称为“栈”的数据结构，它类似于一个放了一摞盘子的容器，每次放进去一个，拿出来的时候就只能从顶端拿一个，不允许从中间插入或抽取，因此被称为“后进先出”（Last In First Out，LIFO）。

5的阶乘递推（进栈）过程的形象表达如下图所示，在实际递归中传递的是参数的地址。

5的阶乘回归（出栈）过程的形象表达如下图所示。

从图中可以很清晰地看到，它首先一步步地把子问题压入栈，直到得到返回值，再一步步地出栈，最终得到递归结果。在运算过程中使用了n个栈空间作为辅助空间。

训练1-34：输入一个整数n，输出斐波那契数列的第n项。

斐波那契数列：1,1,2,3,5,8,13,21,34……

递归式表达式如下：

以F(6)为例，递归求解过程如下图所示。

练习：写一个递归程序，输出1+2+3+…+n。