什么是递归？
递归就是函数自己调用自己！
所谓递归，就是要有递有归！只递不归，会导致程序崩溃！
要在适当的时候终止递归（为了避免崩溃，递归函数一定要包含条件语句）
举例：
#定义一个递归函数 def f(x): //当x=3,调用函数 return x + f(x-1);
返回3 + f(2) , f(2)又返回2 + f(1) , f(1)又返回1 + f(0)…当无限调用函数，需要占用一片叫做栈的内存空间，将一些数据存储到栈中，运行结束，数据从栈中取出来，然而只调用不返回，栈会塞满，从而栈溢出。程序终止！
#定义一个递归函数 def f(x): //x=3 if x > 0: return x + f(x-1); else: return 0;
结果：6
#定义一个递归函数 def f(x): //x=100 if x > 0: return x + f(x-1); else: return 0;
1+2+3+4+…+100=5050
什么是函数嵌套调用与递归？
从一个函数调用另一个函数称为函数的嵌套调用
还有一种情况：
在一个函数体内调用自身称为函数的递归调用
函数递归调用简单例子,run(3),run(2),run(1),代入条件判断是否符合。
#include <stdio.h> #include <stdlib.h> void run(int num){ if(num==0) return; printf("蓝桥杯 我要获奖!\n"); run(num-1); //每递归一次，num减1，最终满足终止条件num==0,递归完成 } void main(){ run(3); //先定义ー个函数，让它执行3次 }
蓝桥杯 我要获奖! 蓝桥杯 我要获奖! 蓝桥杯 我要获奖!
通过这两个例子是不是更好理解函数嵌套调用与递归，go函数调用到run函数，run函数调用到main函数
#include <stdio.h> #include <stdlib.h> void go(){ printf("你可以的\n"); } void run(){ printf("runA\n"); go(); printf("runB\n"); } void main(){ printf("helloworld\n"); run(); printf("欢迎来到蓝桥杯\n"); }
helloworld runA 你可以的 runB 欢迎来到蓝桥杯
有个小技巧：遇到递归用条件语句！
递归的产生
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技 术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与 原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直 接求出其解。这自然导致递归过程的产生。
递归的应用
- 问题的定义是递归的，如阶乘问题。
- 问题的求解过程是递归的，如汉诺塔问题。
- 问题采用的数据结构是递归的，如链表中搜索链表中的元素。
递归的数学公式
- 它是一组等式或不等式；
- 它的第一式给出了函数初始值，称为边界条件；
- 边界条件和递归方程是递归的两个基本要素。
- 它的第二式是用较小自变量的函数值来描述较大自变量的函数值， 称为递归方程；
编写程序：输出斐波那契数列的前30项，要求每行输出5项。
#include <stdio.h> // C语言版本 int fib(int n){// 根据递归式写出函数 if (n==1 || n==2) return 1; else return fib(n-1)+fib(n-2); } int main(){ for(int i=1;i<=30;i++) // 输出前30项 { printf("%-10d",fib(i)); if (i%5==0) // 每行输出5项 printf("\n"); } }
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040
4!的递归
#include <stdio.h> #include <stdlib.h> /* run this program using the console pauser or add your own getch, system("pause") or input loop */ int factorial(int n){ if(n==0) return 1; return n*factorial(n-1); } void main(){ factorial(4); }
还有字符串反转递归！
def reverse_string(string s): if len(s) == 1: return s else: return s[-1] + reverse_string(s[:-1]);
reverse_string('abc'); //调用函数
