下载掌阅APP，畅读海量书库
立即打开
◎ ◎ ◎ ◎ ◎ ◎ ◎ ◎ ◎ ◎
递归调用是函数内部调用自身的过程。递归必须要有结束条件，否则会进入无限递归状态，永远无法结束。
训练1-32： 输入 n 个整数，倒序输出所有整数。
递归包括递推和回归。递推指将原问题不断分解成子问题，直到达到结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始时的原问题，返回原问题的解。
阶乘是典型的递归调用问题，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 。