07《算法入门教程》递归算法

本节内容是递归算法系列之一：递归的介绍，主要介绍了递归的定义，选择了数学归纳法这一数学模型帮助大家可以更好的理解递归的概念，然后明确了一个递归算法必须要具备的三要素，最后说明了一下哪些问题适合应用递归算法求解分析。

递归（Recursion），是计算机科学与技术领域中一种常见的算法思想。

在数学和计算机领域中，递归主要是指在函数的定义中使用函数自身的方法。顾名思义，递归主要包含两个意思， 递 和 归 ，这个是递归思想的精华所在。递归就是有去（递去）有回（归来）。“有去” 是指递归问题可以分解成若干个规模较小、与原问题形式相同的子问题，这些子问题可以和原问题用相同的方法来求解。“有回” 是指这些问题的演化过程是一个从大到小，并且最终会有一个明确的终点，一旦达到终点，就可以从终点原路返回，解决原问题。

很多时候，大家都在思考递归在数学上面应该如何表示了，毕竟对于数学的简单理解比起我们直接写代码起来还是要简单很多的。观察递归，我们会很容易发现递归的数学模型类似于 数学归纳法 ，这个在高中的数列里面就已经开始应用了。数学归纳法常见的描述如下

数学归纳法适用于将需要解决的原问题转换为解决他的子问题，而其中的子问题又可以变成子问题的子问题，而且这些问题都是同一个模型，可以用相同的处理逻辑归纳处理。当然有一个是例外的，就是归纳结束的那一个处理方法不能适用于其他的归纳处理项。递归同样的是将大的问题分解成小问题处理，然后会有一个递归的终止条件，满足终止条件之后开始回归。

数学里面有一个很有名的斐波那契数列，我们在编程求解斐波那契数列的时候就会用到递归的思想，在后续的内部中会具体讲到。

在明确递归的定义及数学模型之后，我们需要掌握递归的三要素：

按照之前的说明，递归应该是有去有回的，这样递归就必须有一个明确的分界点，递归可以在什么时候结束。程序一旦达到这个临界点，就不用继续递归重复下去了。简单来说，递归的终止条件就是为了防止出现无限递归的情况。

如前面说到递归需要一个终止条件一样，在达到递归的终止条件时，需要有一个对应终止条件的程序处理方法。一般而言，在达到递归的终止条件时，对应的问题都是很容易解决的，可以快速的给出问题的解决方案。

递归的本质上还是要将一个大的问题分解成各个逻辑相同的小问题，所以递归过程中一个重要的步骤就是提取递归中重复的逻辑规则，以便利用相同的处理方式进行处理。

按照以上递归的三要素，递归程序的一般处理可以总结成下面的伪代码：

在日常的生活学习中，递归算法一般可以用来解决很多实际问题。回顾一下我们之前学习的排序算法，其中快速排序利用了递归的思想进行解决。总而言之，递归在很多场景中都有应用。

比如说一个常见的对于 *** 作系统里面删除指定路径下的文件夹里内容以及子文件夹里面内容的 *** 作，就可以利用递归思想完成。这个时候递归的终止条件就是判断当前路径是文件，就可以直接删除；发现当前路径是文件夹，则递归调用方法，进入文件夹内部删除里面的文件内容。

总而言之，递归问题在现实学习科研中经常会遇到，这是一种解决问题的思路与方法，将大问题拆分成小问题，然后求解小问题之后回归归纳，得出整个问题的求解结果。

本节主要介绍了递归的定义及基本概念，在学完本节课程之后，需要明白递归的基础逻辑是什么样的，如何自己去设计一个递归算法，在设计一个递归算法时需要考虑到哪些问题，以及我们日常中常见的递归问题。

​是指函数/过程/子程序在运行过程序中直接或间接调用自身而产生的重入现象。
在计算机编程里，递归指的是一个过程：函数不断引用自身，直到引用的对象已知。
使用递归解决问题，思路清晰，代码少。但是在主流高级语言中（如C语言、Pascal语言等）使用递归算法要耗用更多的栈空间，所以在堆栈尺寸受限制时（如嵌入式系统或者内核态编程），应避免采用。所有的递归算法都可以改写成与之等价的非递归算法。
汉诺塔问题，是常见可用递归解决的问题，不过也有非递归的解法。
菲波纳契数列可用递归定义。
以下为求汉诺塔问题的Pascal程序：
procedure Hanoi(n:integer;x,y,z:char);
递归
begin
if n<>1 then begin
Hanoi(n-1,x,z,y);
writeln(x,n,z);
Hanoi(n-1,y,x,z);
else writeln(x,n,z);
end;
end;
上述程序用接近自然语言的伪代码可表述如下：
Hanoi 过程 (整型参数n; 字符型参数 x,y,z);
//注：n 代表本步中要处理的盘子数，x,y,z 分别表示 n 号盘子原来所在柱子、经由柱子、目标柱子
开始
如果 n 不为 1 ，那么：开始
调用 Hanoi 过程 (参数为 n-1,x,z,y);
//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 x 经由柱子 z 移动到柱子 y
输出 x,n,z; //注：表示将 n 号盘子从 x 移动到 z
调用 Hanoi 过程 (参数为 n-1,y,x,z);
//注：这一步表示用本过程方法将剩余 n-1 个盘子从柱子 y 经由柱子 x 移动到柱子 z
结束; //以上程序段就完成了把 n 个盘子从柱子 x 经由柱子 y 移动到柱子 z
否则 输出 x,n,z; //注：若 n 为1 的话本句直接输出表示将 n 号盘子从 x 移动到 z
递归，就是在运行的过程中调用自己。
构成递归需具备的条件：
函数嵌套调用过程示例
1 子问题须与原始问题为同样的事，且更为简单；
2 不能无限制地调用本身，须有个出口，化简为非递归状况处理。
在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

能让人看得懂你的思路，照着你的伪代码能够很清楚你的程序是怎么运行的就ok。伪代码没有固定的格式 关键字什么的。就是体现程序思路而可以忽略一些语法细节的东西
你过三四天再看你写的伪代码能很轻松的照着它写出可以编译运行的程序就行。

我来给个伪代码你参考一下吧
void print(int a[])
{
if (alength == 1) printf("%d", a[0]);
else print(a+1);
}
如不懂可以继续追问

---