一、定义
一个函数直接或间接调用自己
二、函数的调用实现机理
当在一个函数运行期间，调用另一个函数时，在运行被调用函数之前，系统需要先完成三件事：
- 将所有实参、返回地址等信息，传递给被调用函数保存
- 给被调函数的局部变量分配存储区
- 将控制转移到被调函数的入口，
从被调函数返回调用函数之前，系统也会完成三件工作：
- 保存被调函数计算结果
- 释放被调函数数据区
- 依照被调函保存的返回值地址，将控制权限转移给调用函数。
当有多个函数构成嵌套调用时，按照先调用，后返回；后调用，先返回。上述函数之间的传递和控制转移必须借助栈来实现。即：系统将整个程序运行所需的运行空间安排在一个栈中，每当调用一个函数时，就为其在栈顶分配一个存储区，进行压栈操作；每当从一个函数退出时，就释放它的存储区，执行出栈操作，则当正前运行的函数的数据区永远在栈顶位置。
A函数调用A函数 和 A函数调用B函数 在计算机看来是没有任何区别的，只不过用我们日常的思维方式理解比较怪异而己！
三、递归必须满足的三个条件
- 递归必须得有一个明确的终止条件
- 该函数处理的数据规模必须在递减
- 这个转化必须是可解的（无解就死循环了）
四、循环和递归的关系
理论上用循环解决的问题用递归都可以解决，但是用递归解决的问题循环却不一定能解决。
五、递归、循环的优缺点
| 方式 | 优点 | 缺点 |
|---|---|---|
| 递归 | 易于理解 | 速度慢，存储空间大 |
| 循环 | 不易理解 | 速度快，存储空间小 |
六、程序示例
- for循环求阶乘：
#include <stdio.h>
#include <malloc.h>
int main(void) {
int val;
int i, multi;
printf("请输入一个数:\n");
scanf("%d", &val);
for(i = 1; i <= val; i++) {
multi = i * multi;
}
printf("您输入的数的阶乘结果是: %d\n", multi);
return 0;
}
- 递归是有中断条件的：
#include <stdio.h>
void f(int n) {
if(n == 1) //要有退出条件
printf("哈哈\n");
else
f(n-1); //自己调自己
}
int main(void) {
f(3);
return 0;
}
- 求n的阶乘：
/*
求阶乘，假定n >=1
整数有上限
*/
long jieCheng(long n) {
if(n == 1)
return 1;
else
return n * f(n-1);
}
- 求1+2+3+...... + 100的和：
public plus(long n) {
if(n == 1)
return 1;
else
n = n + plus(n-1);
}
void main(void) {
printf("%ld", sum(100));
return 0;
}
七、汉诺塔的由来
- 汉诺塔是源自印度神话里的传说。
- 上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。
- 上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另 一根柱子上。并且规定，在小圆盘的上面不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
- 有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有 人相信婆罗门至今还在一刻不停地搬动着圆盘。
100个盘子，你要是能搞定上面的99个，最后的就搞定了；
99个盘子，你要是能搞定上面的98个，第99个也搞定了
。。。。。。
3个盘子
2个盘子
1个盘子
八、汉诺塔的伪代码
if( n > 1 ) {
先把柱子上的前n-1个盘子从A借助C移到B
将A柱子上的第n个盘子直接移到C
再将B柱子上的n-1个盘子借助A移到C
}
九、汉诺塔的程序实现
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
/**将A上的盘子借助B移到C上去*/
void hannuota(int n, char A, char B, char C) {
//如果是1个盘子，直接将A柱子上的盘子移到C
//否则
// 先将A柱子上的N-1个盘子借助C移到B
// 直接将A柱子上的第N个盘子移到C
// 最后将B柱子上的n-1个盘子借助A移到C
if(1 == n) {
printf("将编号是%d的盘子直接从%d柱子移到%d柱子", n, A, C);
}
else
{
hannuota(n-1, A,C,B); //将A上的n-1个盘子借助C移到B
printf("将编号是%d的盘子直接从%d柱子移到%d柱子", n, A, C);
hannuota(n-1,B,A,C); //将B上的n-1个盘子接祖A移到C
}
}
int main(void) {
char ch1 = 'A';
char ch2 = 'B';
char ch3 = 'C';
int n;
printf("请输入要移动盘子的个数：");
scanf("%d", &n);
hannuota(100, ch1, ch2, ch3);
}
十、汉诺塔总结
【讲阶乘】像这种没有明确执行次数的问题，都是用递归来解决)
【讲汉诺塔)这不是线性递归，这是个非线性递归
n=l 1
n=2 3
n=3 7
........
........
n=64 264-1 , 这是个天文数字，就算世界上最快的计算机也解决不了。
汉诺塔的复杂度是2n-1
问题很复杂，但真正解决问题的编码就只有三句
规约法、回溯法、递归法 这是算法领域很重要的集中思路
计算机把你360度扫描一下，但如果你有一次冲它笑了一次，计算机就傻眼了，又不认识了。但人则不一样，如果你当初深深地望了默认一眼，可能若干年后也忘不掉。
十一、递归的应用
- 树和深林就是以递归的方式定义的
- 树和图的很多算法就是以递归来实现的
- 很多数学公式就是以递归定义的（斐波那契数列）
十二、数据结构关于（非）线性结构、逻辑结构、物理结构的总结
(1)逻辑结构：
-
线性
- 数组
- 链表
- 栈和队列是一种特殊的线性结构。
线性结构的物理存储是数组和链表，不能说是栈和队列；
栈和队列不是线性结构的一种物理存储方式
而是线性结构的一种特殊的表现形式
或者说是它的一个具体的应用。
- 非线性
- 树
- 图
(2)物理结构
如何把逻辑的东西保存到计算机里面。
十三、线性结构和非线性结构的思考总结
线性结构的算法已经非常成熟。在所有的编程语言里（Java，C++，C#，Python），对链表和数组操作的算法都已经很完善了。已经将相应的工具类造出来了。eg：ArrayList LinkedList。但是Java里面你看不到树 和图 的相关工具类。比如：你看不到有相关的XXXTree ，XXXGraph类。因为非线性结构太复杂了，其操作复杂度远远大于线性结构的数组和链表。人类发展到现在这个水平对非线性结构的研究还远远不成熟。连Sun公司都造不出来，因为算法不成熟。
当然Java里有TreeSet，只不过是利用了一个树的排序的方式实现的容器，本质上已经不能算作树了，放数据的时候利用了树的排序算法，已经拥有了一些🌲的知识，但是本质上并不是🌲。
树和图实在太复杂了，到目前为止，还没有任何一家公司能造出以🌲和图为核心的工具。有应用，但是不广泛，为什么不广泛？不是说不重要，而是对🌲进行排序、操作、增加、删除、遍历 这些算法都不是很好，没有一个很好的，很完善的，可以执行强的又十分健壮的算法（太复杂了）。
线性结构是一种逻辑结构，用一根线牵起来，属于我们大脑中的一种存储数据的方式，跟我们计算机没有任何关系。
十四、为什么学数据结构难？
因为计算机的内存是线性一维的，而现实生活中的问题是复杂的，如何把复杂的问题用计算机的一维线性内存方式实现，这是困难的，因为现实中的问题千变万化。
如果硬件设备能建造的和现实问题一一对应起来的话那就简单了。如何保存这个东西本身已经是个问题了：先建立一个数学模型，然后把这个数学模型变成一个线性的东西。
