函数递归调用原理

1. 什么是递归2. 递归的举例3. 递归与迭代1. 什么是递归递归就是一种解决方法在C语言中递归就是函数调用自己。下面是一个简单的递归C语言程序#include stdio .h int main() { printf(hello world\n); main();//main函数中又调用了main函数 return 0; }如上注释main会递归调用自己这样只是为了展示递归的基础程序不是为了解决问题所以程序会进入死循环导致栈溢出。1.1.递归的思路我们可以把它当做跟forwhile等循环解决问题一样当成一种解决问题的方法但它主要是把大问题化解成小问题主要思路主要是递推跟回归接下来我带你们慢慢体会1.2.递归的限制条件跟forwhile一样它也有限制条件不过它只有两个限制条件。·递归需要有个限制条件这个限制条件将关乎递归的结束·每次递归过后都越来越接近限制条件1.3.函数递归的优缺点优点函数递归只需少量的程序就可描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。缺点①如果函数递归使用不恰当会导致栈溢出②函数不返回函数对应的栈帧空间就一直占用所以如果函数调用中存在递归调用的话每一次递归函数调用都会开辟属于自己的栈帧空间直到函数递归不再继续开始回归才逐层释放栈帧空间。这样就会大大占用栈帧空间同时大大降低代码的执行效率。关于函数栈帧如下在C语言中每一次函数调用都需要为本次函数调用在内存的栈区申请一块内存空间来保存函数调用期间的各种局部变量的值这块空间被称为运行时堆栈或者函数栈帧。2. 递归的举例与实现我们了解了递归的底层逻辑接下来我们来看几个程序来看一下递归如何实现2.1求n的阶乘题目∶计算n的阶乘不考虑溢出。2.1.1分析跟代码实现n的阶乘的公式:n!n*(n-1)!从中我们发现这个思路就是把一个数的阶乘换成比它小一个的数的阶乘然后一层一层把大问题细小化其中的限制条件就是n0。上面的函数Fact函数就是递归调用的函数其中的特殊情况就是当n0时Fact1那我们就可以写出这个函数假设Fact(n)就是求n的阶乘那么Fact(n-1)就是求n-1的阶乘函数如下∶int Fact(int n) { if(n0) return 1; else return n*Fact(n-1); }运行结果不需要考虑n太大的问题n太大存在溢出。如果还是觉得难懂的话下面有个图可以直观体现出递归思路而如果我们不用递归的话就只用循环的话一层循环就可以了代码如下#define _CRT_SECURE_NO_WARNINGS 1 #includestdio.h int main() { int i 0; int n 0, end 1; scanf(%d, n); for (i 1; i n; i) { end * i; } printf(%d, end); return 0; }2.2顺序打印输入一个整数的每一位例如∶输入1234 打印1 2 3 42.2.1分析和代码实现解题思路∶当输入n的值是一位数输出的n反之则拆分n的每一位。而我们就需要取模跟取余的方式得到n的每一位例如1234%1041234%10123整型会自动约分为整数然后一步一步得到每一位。但这种情况如果直接输出的话就会输出4 3 2 1所以我们可以用递归的方式反向输出这样就可以输出1 2 3 4了可以用下面的表达式来体现递归的方法Print(1234)Print(123) printf(4)Print(12) printf(3)Print(1) printf(2)printf(1)Print函数的限制条件是当数字为一位数时返回所有值然后递归结束。下面是代码实现∶#define _CRT_SECURE_NO_WARNINGS 1 #includestdio.h int Print(int x) { if (x 9) { Print(x / 10); } printf(%d , x % 10); } int main() { int n 0; scanf(%d, n); Print(n); return 0; }2.3模拟实现strlen函数例如∶输入abc 输出32.3.1分析和代码实现首先我们要知道strlen函数是计算字符串‘\0’之前的长度但我们如果要实现的话就需要设计一个my_strlen函数这个函数每遇见一个衣服函数值加1直至到‘\0’结束可以用下面的表达式来体现递归的方法my_strlen(abc)--------------这里是指针在移动1my_strlen(bc)1my_strlen(b)1my_strlen(‘\0’)当满足我们的限制条件’\0’时返回0然后回归my_strlen函数限制条件就是‘\0’下面是代码实现int my_strlen(char* str) { if (*str ! \0) { return 1 my_strlen(str 1);//strlen函数的模拟实现方式 } return 0; } int main() { char arr[] abc; int ret my_strlen(arr); printf(%d, ret); return 0; }2.4求n的k次幂例如∶输入3 3 输出272.4.1分析和代码实现解题思路∶首先对k进行分析当k0时无论n为几函数最后返回值都为1当k1时每一次递推就乘以n而k-1直至k0。其中有一个隐含条件就是k不会0。同样也可以用下面的表达式来体现递归n3 k3Pow33n*Pow33-1n*Pow32-1n*31-1当k0时函数返回1下面是代码实现int Pow(int x, int y) { while (y) { return x*Pow(x, y - 1); } } int main() { int n 0, k 0; scanf(%d %d, n, k); int cPow(n, k); printf(%d, c); return 0; }3.递归与迭代我们看到的许多问题是以递归的形式进⾏解释的这只是因为它⽐⾮递归的形式更加清晰但是这些问题的迭代实现往往⽐递归实现效率更⾼。当⼀个问题⾮常复杂难以使⽤迭代的⽅式实现时此时递归实现的简洁性便可以补偿它所带来的运行时开销。二者是相辅相依的。下面我们用一个题来看下他们之间的区别3.1斐波那契数列递归实现与迭代实现3.1.1递归分析和代码实现解题思路∶斐波那契系数是前两项加起来等于后一项11235813…,所以我们可以以n2为限制条件当n1或2时返回1然后到n3项时就是n1项和n2项之和然后依次往后推即Fib(n)就是Fib(n-1)和Fib(n-2)之和。可以用下面的表达式来体现递归Fib(n)Fib(n-1) Fib(n-2)Fib(n-2)Fib(n-3) , Fib(n-3)Fib(n-4)…一直递推下去直至到Fib(1)和Fib(2)返回值为1然后回归得到第n个斐波那契数。下面还有一个图来帮助我们设计Fib函数递归代码实现∶int Fib(int x) { if (x 2) { return 1; } else { return Fib(x - 1) Fib(x - 2); } } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d, n); return 0; }3.1.2迭代分析和代码实现解题思路∶可以参考上面递归实现的思路我们可以用三个变量相互替换来解决n1为第一项n2为第二项tmp为第三项运用while()循环每一次循环n就减1直到n2最后输出tmp。限制条件当n2输出的值都是1反之当n2时循环开始n2时循环结束下面是迭代代码实现int Fib(int n) { int a 1; int b 1; int c 1; if (n 2) { return 1; } while(n2) { c a b; a b; b c; n--; } return c; } int main() { int n 0; scanf(%d, n); int ret Fib(n); printf(%d, ret); return 0; }3.2斐波那契数列中递归与迭代的区别当我们尝试输入50时我们可以发现递归的计算时间会非常长这个计算所花费的时间说明递归的效率是非常低的这是为什么呢下面一张图可以带给我们答案其实递归程序会不断的展开在展开的过程中我们很容易就能发现在递归的过程中会有重复计算⽽且递归层次越深冗余计算就会越多。而这些程序的计算结果不会共享每次计算都会重新计算这是因为函数栈帧的创建与销毁每次调用函数都会在函数栈帧上开辟空间同时完成函数是有要销毁这些空间。这样就大大降低了运行效率。而当我们用迭代的方法时会发现其实现的效率就比递归的效率高多了这是为什么呢这是因为每一次循环n1,n2,tmp会被赋值代码执行次数大大减少也就大大提高了代码的执行效率。