前言
一、函数递归
1.什么是递归?
(1)程序调用自身的编程技巧称为递归（ recursion）。
(2)递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的
(3)一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略
递归的主要思想方式是:把大事化小
2.递归的两个必要条件
(1)存在限制条件，当满足这个限制条件的时候，递归便不再继续
(2)每次递归调用之后越来越接近这个限制条件
3.最简单的递归例子
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> //函数递归 int main() { printf("hehe\n"); main(); return 0; }
屏幕上会无限循环打印hehe:
并且出现报错:
Stack overflow:栈溢出
原因:
main函数中无限调用main()函数,又因为每次函数调用都得向栈区申请空间,这样的话一直在栈区申请空间,迟早栈区的空间会被耗干,当被耗干的那一刻,就会报错Stack overflow
结论:递归虽然是自己调用自己,但是绝不是无节制的自己调用自己,
内存的划分:栈区,堆区,静态区
注意:那么函数在调用过程中是如何向栈区申请空间的?参数是如何传参的?传过去函数是如何使用的?
内容较多,请小伙伴们持续关注我的博客,后面会出相关内容哦~💕
4.递归练习:
(1)接受一个整型值（无符号），按照顺序打印它的每一位。
例如：
输入：1234，输出 1 2 3 4
a.代码讲解
//思路: 观察数字
// 1234
// 1234%10=4
// 1234/10=123 123%10=3
// 123/10=12 12%10=2
// 12/10=1 1%10=1
//%u—无符号的整数
//%d—有符号的整数
//1.首先列出框架int main(){}
//2.控制不同的类型%u
//3.将题目封装成一个函数Print()
//4.通过观察可以发现Print()函数最容易打印出来的是4
//5.分析:
// Print(1234)拆解为:一层一层往下拆数字
// Print(123) 4 先把123打印在屏幕上,再把4打印出来
// Print(12) 3 4 先把12打印在屏幕上,再把3打印在屏幕上
// Print(1) 2 3 4 先把1打印在屏幕上,再把2打印在屏幕上
void Print(unsigned int n) { if (n > 9) //n>9:说明是两位数以上的数字. //如果是一位数,就不用拆分.两位数以上的数字才要拆分,递归的条件很重要 { Print(n / 10); //Print是自定义函数,1234传进来之后>9,接着调用Print(123),123>9,调用Print(12),12>9,调用Print(1),1<9,不执行if语句,打印出(1%10)结果1, //逐层返回,回到Print(12),接下来打印(12%10)结果2 //逐层返回,回到Print(123),接下来打印(123%10)结果3 //逐层返回,回到Print(1234).接下来打印Print(1234%10)结果4 //Print(n / 10); /10的操作很重要,如果没有/10的操作,一直传入的n不断进入递归 } printf("%d ", n % 10); } int main() { unsigned int num = 0; //unsigned类型的变量 scanf("%u", &num); //%u---无符号的整数 (说明不能输入负数,即使输入负数也把它当做正数来看待) Print(num); //Print()函数负责把num的每一位打印在屏幕上 return 0; }
b画图讲解
递归: 递推, 回归
拆分概况:
(2)编写函数不允许创建临时变量，求字符串的长度。
a.如果单一的求字符串的长度
#include<stdio.h> #include<string.h> //strlen头文件 int main() { char arr[10] = "abcdef"; int len = strlen(arr); printf("%d\n", len); return 0; }
b.如果单一的写一个函数求字符串的长度
//先写一个函数求字符串长度 //但是该方法创建了临时变量 #include<stdio.h> #include<string.h> int my_strlen(char* str) { //str接收a的地址 int count = 0; //为了统计字符串的个数创建一个临时变量count while (*str != '\0') { //strlen统计的是字符串中\0前字符的个数 count++; //计数器++ str++; //地址++,看当前的下一个字符是不是\0 } return count; } int main() { char arr[10] = "abcdef"; //数组内容:[a b c d e f \0 - - -] int len = my_strlen(arr); //数组名是数组首元素的地址,所以把a的地址传给函数 printf("%d\n",len); return 0; }
c.题目正解:编写函数不允许创建临时变量，求字符串的长度
//不创建临时变量的思路:
// 当发现字符串第一个字符不是\0的时候,字符串的长度应该为1 总长度=1+后面字符串的长度
// my_strlen(“abcdef”);拆分过程
// 1+my_strlen(“bcdef”);
// my_strlen(“bcdef”);拆分为: 1+my_strlen(“cdef”);
// my_strlen(“cdef”); 拆分为: 1+my_strlen(“def”);
// my_strlen(“def”); 拆分为: 1+my_strlen(“ef”);
// my_strlen(“ef”); 拆分为: 1+my_strlen(“f”);
// my_strlen(“f”); 拆分为: 1+my_strlen(" ");
#include<stdio.h> int my_strlen(char* str) { if (*str != '\0') //递归的条件 让它不断逼近跳出递归的条件 return 1 + my_strlen(str + 1); //不能写成return 1 + my_strlen(str + +); str后置++:(先使用后++)先是把str的地址传出去之后,str再++. 传出去的str没有变化,,和原来一样,没用,是错的死递归 //但是也不要写成++str,因为这样的话在原来函数中的str被修改了 else return 0; } int main() { char arr[10] = "abcdef"; //[a b c d e f \0 - - -] int len = my_strlen(arr); printf("%d\n", len); return 0; }
画图讲解:(比如"abc\0")
**注意:**在递归的使用中尽量不要使用前置++或者后置++,会有副作用导致出错的.
int my_strlen(char* str) { if (*str != '\0') //递归的条件 让它不断逼近跳出递归的条件 return 1 + my_strlen(str + 1); //不能写成return 1 + my_strlen(str + +); str后置++:(先使用后++)先是把str的地址传出去之后,str再++. 传出去的str没有变化,,和原来一样,没用,是错的死递归 //但是也不要写成++str,因为这样的话在原来函数中的str被修改了 else return 0; }
通过窗口监视观察:
二、函数迭代
循环是迭代的一种.循环法也叫迭代法.
下面我们通过例子来学习:
1.计算n的阶乘
(1)解法一:循环的方法(迭代法)
int fac(int n){ int i = 0; int ret = 1; for (i = 1; i <= n; i++) { ret = ret * i; } return ret; } int main() { int n = 0; scanf("%d", &n); int ret = fac(n); printf("%d\n", ret); return 0; }
(2)解法二:递归法
//fac(n) n<=1;fac=1
// n>1;fac=n*fac(n-1)
int fac(int n) { if (n <= 1) return 1; else return n * fac(n - 1); } int main() { int n = 0; scanf("%d", &n); int ret = fac(n); printf("%d\n", ret); return 0; }
2.求第n个斐波那契数。（不考虑溢出）
什么是斐波那契数列?
//1 1 2 3 5 8 13 …
//特点是一个数是前两个数之和
求第n个斐波那契数,前提是给出前两个数
//设第n个斐波那契数Fib(n)
n<=2, Fib=1
n>2, Fib=Fib(n-1)+Fic(n-2)
(1)解法一:递归的方法(效率低)
int fib(int n) { if (n <= 2) return 1; else return fib(n - 1) + fib(n - 2); } int main() { int n = 0; scanf("%d",&n); int ret = fib(n); printf("%d\n",ret); }
当输入5时,结果如下:
当输入一些较小的数字,结果快速算出且正确
但是当输入50时:
发现一直没有返回结果,但是程序在运行,说明程序计算繁忙,这是为什么呢?
比如:在求第40个斐波那契数时,要计算第39个和第38个斐波那契数;计算第39个斐波那契数时,要先计算第38个和第37个斐波那契数;计算第38个斐波那契数时,要先计算第37个和第36个斐波那契数…
发现会计算大量重复的数据,我们可以通过代码计算一下在求第40个斐波那契数时,第三个斐波那契数被重复计算了多少次?
int count = 0; int Fib(int n) { if (n == 3) count++; if (n <= 2) return 1; else return Fib(n - 1) + Fib(n - 2); } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); printf("count=%d\n", count); }
由此可见,仅仅是计算第三个斐波那契数的次数就达到3900多万次.
说明在这个问题上用递归的方法解决效率较低
注意:使用递归时出现栈溢出的问题:
我们要去看一下是不是死递归了或者是不是在栈里面开辟的空间过多了.
系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
(2)解法二:迭代法(最佳)
不断用前两个数相加得到第三个的方法求
//迭代的方式----把一件事情反复去做:不断用前两个数相加得到第三个的方法求
//当求第三个斐波那契数时,将a,b赋值1,求出c 共进行一次循环
//当求第四个斐波那契数时,向上一次b的值赋值给a,将上一次c的值赋值给b,求出c 共进行两次循环
//…
int Fib(int n) { int a = 1; int b = 1; int c = 1; //c的初始值设为0时候会有漏洞,因为当n=1或者n=2时传进来不进入while循环,return c的话c=0,不符合斐波那契数列 //所以c的初始值设为1 while (n>=3) { //当n=1或者n=2时不需要进来 c = a + b; a = b; b = c; //n--很重要,如果没有n--,n就会进入while的死循环 n--; //n=3时,n--变为2,不再进入循环 } return c; //当while循环停下来的时候要返回结果c,c就是要求的第n个斐波那契数 } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
代码的效率大大提高,只不过结果是错的,因为范围有限,放不下太大的数字,如果一直算下去,计算的结果溢出了,溢出之后,而恰好符号位是1的话,那我们看到的就是负数.
但是在不溢出的情况下,计算结果是非常快的,同时这道题目也声明了不考虑溢出的情况,这样写是完全没问题的啦~.🤞
3.汉诺塔问题
4.青蛙跳台阶问题
递归经典题目3.4请小伙伴们关注后续博客,将详细讲解.
总结
今天的内容你学会了吗小伙伴们?💕💕
如果哪里写的有问题,欢迎大家帮我指正.
最后,如果对您有所帮助的话,可以留下关注点赞收藏哦~🥰💕❤️
