在给女儿备考计算机软件编程等级考试时系统地研究了一下关于递归编程的思想，相关内容系统地整理如下。

如何帮助小朋友快速掌握递归的思想?

好的类比能帮助小朋友更好地理解一些比较陌生且抽象的概念，如通过曹冲秤象的例子讲解微积分思想，那么如何向低年级的小朋友讲解递归的思想呢？网上有朋友举了一个非常好的例子就是在电影院看电影时确定自己的座位的事情。

如图所示假设小哥哥在电影开演后进入电影院后找不到自己的座位，问身边的小姐姐“这是第几排”，小姐姐也不清楚便依次向前询问，问至第一排的观众后依次向后反馈结果，“我是第一排”、“我是第二排”、···，最终确定自己座位所在排数。

在这个过程中充分反应了“传递”（询问）和“回归”（反馈）的思想，故将这种现象称为“递归”。

除了上面的例子外，生活中还有很多可以帮助小朋友理解递归思想的例子，比如老和尚给小和尚讲故事的童谣，俄罗斯套娃，对着镜子拍照，圣诞树的叶子等等。

迭代与递归是人类用智的两种不同思维模式

当然本例的小哥哥也可以不依赖问别人，自己走出来从第一排开始逐排地数，直至数到自己所在的位置从而得出自己座位所在排数，只是这种方式是一种常用的用智方式，即由小到大，由少到多，由简单到复杂的迭代(iteration)方式，比如人都是先学习加减法，再学习乘除法，最后学习微积分。数学归纳法其实就是一种迭代，从一个简单的起点，推广到一般情况。

递归(recursion)，则是一种反人类的逆向思维，因为这种思维逻辑甚至是反常识的举一个简单的计算5!的例子。迭代的思维一般是按照1x2x3x4x5的顺序计算，而递归的思维则是5! = 5x4!，那么4!是什么呢？不重要，因为4! = 4x3!，这样一直往前推，直到1! = 1。这个时候再把每个值往回代入计算，就能得到最终的结果。

为什么要培养和训练递归的思维模式?

想必你会说，上面的例题用迭代就能轻松写出来，为何还需要使用递归呢？

的确能用递归解决的问题，用迭代也能解决，而且递归比迭代的运算速度要慢，因为递归需要逐层调用函数，占据系统内存，当 递归层级较深时，对性能消耗较大，往往不推荐使用。

那递归存在的意义是什么？递归是为了将复杂问题简单化提供的解题思路，对于简单问题，一眼便能看出“循环迭代算法”，但对于一些抽象问题，普通迭代循环法有时很难立刻给出解决方案，相反如果采用了递归的思想答案可能会出乎意料的简单，这里举两个简单例子说明。

例题一：某人需要走上10级台阶，有两种走法，走法A：一步1个台阶；走法B：一步2个台阶。两种走法可以任意交替使用，问走上10级台阶共有多少种方法？

这个问题很难直接看出迭代循环的解题思路，我们不妨从递归的角度尝试解决：

当走上第10级台阶只差最后一步时，存在有两种可能：

第1种：从 第8级 —> 第10级（一步2个台阶）

第2种：从 第9级 —> 第10级（一步1个台阶）

假设：从 第0级 —> 第8级，有 x种走法；

1，1，1，1，1，1，2，2

1，1，1，1，1，2，1，2

1，2，1，1，1，2，2

1，2，1，2，2，2

·······

// 穷举不尽，共 x 种，每种走法的最后一步都是 2(个台阶)

假设：从 第0级 —> 第9级，有 y种走法；

1，1，1，1，1，1，1，2，1

1，1，2，1，1，2，1，1

1，2，1，2，2，1，1

1，2，2，2，2，1

·······

// 穷举不尽，共 y 种，每种走法的最后一步都是 1(个台阶)

那么，从 第0级 —> 第10级，共有 x + y种走法。故10级台阶走法 = 9级台阶走法 + 8级台阶走法，即 f(10) = f(9) + f(8);

所以我们需要的函数关系式是 f(n) = f(n - 1) + f(n - 2)，由此可以写出递归函数:

int fn(n)

{

if(n === 1 || n === 2){ return n; }

return f(n - 1) + f(n - 2);

}

由此可见，一旦掌握了递归的思想，即使是很抽象的问题依赖其内部的递归规律，问题很快就会迎刃而解。

例题二、汉诺塔问题，目标是要把所有的盘子从最左边（柱子A）移动到最右边（柱子C），条件是:1）每次只能移动一个盘子；2）小盘子只能放在大盘子之上。

汉诺塔问题更加抽象，但是如果从递归角度来考虑问题就非常简洁，一共分成三步即可。

第一阶段：（n-1）：A—>B（把所有的n-1个盘子从A移动到B上）;

第二阶段：n： A—>C（把最底下的n号盘从A移动到C上）;

第三阶段：（n-1：）B—>C（把n-1个盘子从B移动到C上）。

完整代码:

void hanoi(int n, char A, char B, char C)

{

if (n==1)

printf("将编号为1的盘子从%c移到%c\n",A,C);

else

{

// 1 将A上编号为1到n-1的圆盘移到B，C作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,A,C,B);

hanoi(n-1,A,C,B);

// 2 将A上编号为n的圆盘移到C

printf("将编号为%d的盘子从%c移到%c\n",n,A,C);

// 3 将B上编号为1到n-1的圆盘移到C，B作辅助塔

printf("hanoi(%d,%c,%c,%c)\n",n-1,B,A,C);

hanoi(n-1,B,A,C); //

}

}

递归编程需要注意的关键点有哪些?

运用递归思维解决问题，需要注意递归思想的三要素：

第一要素：明确你这个函数想要干什么

对于递归，我觉得很重要的一个事就是，这个函数的功能是什么，他要完成什么样的一件事，而这个，是完全由你自己来定义的。也就是说，我们先不管函数里面的代码什么，而是要先明白，你这个函数是要用来干什么。

第二要素：寻找递归结束条件

所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。也就是说，我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。

第三要素：找出函数的等价关系式

第三要素就是我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。

例如，f(n) 这个范围比较大，我们可以让 f(n) = n * f(n-1)。这样，范围就由 n 变成了 n-1 了，范围变小了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。

说白了，就是要找到原函数的一个等价关系式，f(n) 的等价关系式为 n * f(n-1)，即

f(n) = n * f(n-1)。

递归算法的编程模型

在我们明确递归算法设计三要素后，接下来就需要着手开始编写具体的算法了。在编写算法时，不失一般性，我们给出两种典型的递归算法设计模型，如下所示。

模型一： 在递去的过程中解决问题

模型二： 在归来的过程中解决问题

几个与递归有关的经典题目

要让小朋友真正掌握并熟练运用递归思维模式，还需要结合小朋友的兴趣练习一些经典的题目，这里列举了几个与递归有关的经典题目如下。

一、组合问题：从m个数字中取出n个数字，有多少种组合？分别是什么？

二、全排列问题：m个数字一共有多少种排列？分别是什么？

三、跳马问题

四、数独问题