注：转载请标明原文出处链接：https://xiongyiming.blog.csdn.net/article/details/105643504

1 什么是递归

一个函数在它的函数体内调用它自身称为递归调用，这种函数称为递归函数。
简单的来说：递归就是一个函数自己直接或间接调用自己。

常见可以使用递归的例子有：

1. 1+2+3+4+…+100的和
2. 求阶乘
3. 汉诺塔

2 举例说明递归

2.1 例1

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> void f(); void g(); void k(); int main() { f(); system("pause"); return 0; } void f() { printf("FFFFn"); g(); printf("1111n"); } void g() { printf("GGGGn"); k(); printf("2222n"); } void k() { printf("KKKKn"); printf("3333n"); } 

运行结果

2.2 例2

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> void f(int n); int main() { f(7); system("pause"); return 0; } void f(int n) { if (n == 1) printf("我自己调用自己n"); else { printf("n=%dn",n); f(n - 1); } } 

运行结果

2.3 例3——阶乘

方式1——使用循环的方式

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> int main() { int val; int i, mult = 1, s; printf("请输入一个数字："); printf("val="); scanf("%d", &val); for (i = 1; i <= val; ++i)   mult = mult * i; printf("%d的阶乘是：%dn", val, mult); system("pause"); return 0; } 

运行结果

方式2——使用递归的方式

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> long f(long n) { if (1 == n) return 1; else return f(n - 1)*n; } int main() { int val; printf("请输入一个数字："); printf("val="); scanf("%d", &val); printf("%d的阶乘是：%dn", val,f(val)); system("pause"); return 0; } 

运行结果

2.4 例4——1+2+3+…+100之和

方式1——使用循环的方式

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> int main() { int sum = 0; for (int i = 1; i <= 100; i++)   sum = sum + i; printf("1+2+3+...+100 = %dn", sum); system("pause"); return 0; } 

运行结果

方式2——使用递归的方式

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> //假定n的值是大于或等于1的值 long sum(long n) { if (1 == n) return 1; else return sum(n - 1) + n; } int main() { printf("1+2+3+...+100 = %dn", sum(100)); system("pause"); return 0; } 

运行结果

2.5 例5——汉诺塔

#pragma warning( disable : 4996) #include<stdio.h> #include<iostream> #include<malloc.h> #include<string.h> #include<stdlib.h> //汉诺塔 void hannuota(int n, char A, char B, char C) { /*伪代码  如果仅有一个盘子   直接将A柱子上的盘子从A移到C  否则   先将A柱子上的n-1个盘子借助C移到B   直接将A柱子上的盘子从A移到C   最后将B柱子上的n-1个盘子借助A移到C  */ if (1 == n) { printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C); } else { hannuota(n - 1, A, C, B); printf("将编号为%d的盘子直接从%c柱子移到%c柱子n", n, A, C); hannuota(n - 1, B, A, C); } } int main() { char ch1 = 'A'; char ch2 = 'B'; char ch3 = 'C'; int n; printf("请输入要移动盘子的个数 :"); scanf("%d", &n); hannuota(n, 'A', 'B', 'C'); system("pause"); return 0; } 

运行结果

3 递归必须满足三个条件

1. 递归必须得有一个明确的终止条件；
2. 该函数所处理的数据规模必须在递减；
3. 这个转化必须是可解的；

4 循环和递归的比较

1. 理论上，所有的循环都可以转化成递归，但是用递归能解决的问题不一定能用循环解决。

2. 递归：易于理解，速度慢，存储空间大

3. 循环：不易理解，速度快，存储空间小

5 递归的应用

1. 数和森林就是以递归的方式来是实现的；
2. 数和图的很多算法就是以递归的方式来定义的；
3. 很多数学公式就是以递归的方式定义的；