C进阶函数的递归

文章目录

一，函数递归的介绍

二，考虑仅变量的递归

三，考虑指针与地址的递归

四，迭代与递归的选择与二者之间的利与弊

五，经典题目：汉诺塔问题（感兴趣可以去看看视频学习一下，这个文章不太好描述）

前言

此类算法可以简化代码的书写量，进而可以更加简洁的书写自己的代码

一.函数递归的介绍

程序调用自身的编程技巧称之为递归

(主要思考方式：把大事化小事)它通常把一个大型复杂的问题层层转换为一个一个与问题相似规模较小的问题

（注：1.vs上面有一个快速注释的按键可以利于调试 2.%u是指输出的内容不会包含正负号，数字总是大于0）

二，考虑仅变量的递归

例题：接受一个整形的值（无符号），按照顺序打印他的每一位

我们使用正常的思路来解这个题目（迭代法）

注：迭代法就是我们平时所用的for while循环那些

#include<stdio.h>int main()
{int num = 0;scanf("%d", &num);while (num) {printf("%d ", num % 10);num = num / 10;}return 0;
}

我们利用了这个迭代法来解决了这个问题（vs2019测试）

接下来我们来用迭代法来实现这个功能

迭代法的思想：我们要把一个大型复杂的问题层层转换为一个一个与问题相似规模较小的问题

我们用这个思想，就可以把这个打印1234逐步变成一个很easy的问题，接下来我们用代码实现一下这个思想

#include<stdio.h>
void print(unsigned int num) {if (num > 0) {print(num / 10);printf("%d ", num%10);}
}
int main() {unsigned int num = 0;scanf("%d", &num);print(num);return 0;
}

这里我们用vs2019测试

这里是用来递归的思想，注意我们在while循环里面，这个里面第一次执行完print的时候没有立马执行printf，如果第一次while循环执行到print的时候，如果直接打印了，那么这个时候不是1在前面了，是4在前面，我们利用一个图分析

这样我们就实现了递归，当然如果把print和printf倒着换过来，这样就是先打印4然后再进行递归

这样就可以实现4 3 2 1的结果了

从这个程序我们就可以知道递归是一层一层进行像剥洋葱一样来进行实现程序的进行，我们可以巧用再递归的上面写程序还是下面写程序，这些都是可以巧用的，有助于我们来写程序（n>0这个条件十分常用）

对于此案例的递归总结

1，如果没有（n>0）这个条件的话就会报错，Stack overflow

栈溢出的是由于无递归条件使程序进入了死循环，这样就会出现栈溢出的现象

2.如果没有%10.也会出现Stack overflow

这样我们就可以学习到我们应该要有两个限制递归的条件

1.限制条件1：满足这个条件，递归将不再继续进行（一般用if语句）

2.限制条件2：满足这个条件，每次的递归都会越来越接近限制条件1然后来结束递归（一般放入递归函数里面，如这里的print（num%10））

这里我们在使用和这个递归的时候要考虑到他怎么在我们内存里面存活下来的，因为我们每次都是可以调用到上一次的值，上一次的值是并没有销毁的而是保存到内存里面的，所以这个递归是很容易出现Stack overflow的，因为每一都是像剥洋葱一样剥下来的，所以值都没有销毁，当然来有Stack overflow说明这个是存在STACK里面的，我们来看一个图来了解一下内存

那么我们该怎么将一个复杂的问题转换为一个规模较小的问题呢？

我们只需记得有来有回即可我们来看一个图来理解有来有回这个方法

这个图是根据上面的一个例子所画出来的，这样就可以更好的帮助我们来了解这个方法

对于有来有回，我们利用一个例子来加深这个记忆

#include<stdio.h>
void story(int a) 
{if (a > 0) {printf("我爱你%d\n", a);story(a - 1);printf("说了几次我爱你了，我就是不喜欢你，我有喜欢的人%d\n", a);}elseprintf("说完之后，听到了ta的话心碎了\n");
}
int main() 
{int a = 0;scanf("%d", &a);story(a);
}

这个代码当我们输入5的时候(用vs2019测试)

我们来看这个输出的顺序，首先我们输出我爱你，我爱你后面的数字是倒序的说明是正常先进行执行，但是说了几次我爱你了，我就是不喜欢你，我有喜欢的人,这个后面数字是正序的，说明他是先要一直执行，后面递归结束的时候，在进行输出数字，这个说完之后，听到了ta的话心碎了这话我们就是在结束递归的时候，else先执行，因为a=0的时候也有一个结果，所以这个是比说了几次我爱你了，我就是不喜欢你，我有喜欢的人先执行的

（总结：这里的我爱你是表示来的，说了几次我爱你了，我就是不喜欢你，我有喜欢的人是表示回的，一个男生给女生表白表示来，女生的回话表示回，中间else表示他们之间的一个值，表示他们之间的一个过程ta心碎了）

三，考虑指针与地址的递归

例题：编写函数求字符串的长度

我们用迭代法（计数法）：

#include<stdio.h>int my_strlen(const char* str) {int count = 0;while(*str != '\0') {count++;*str++;}return count;
}
int main()
{int len = my_strlen("abc");printf("%d", len);return 0;
}

这里很简单，不懂可以自己看看，用vs2019测试

接下里我们用递归法来解这个问题（不允许创建临时变量）

#include<stdio.h>int my_strlen(const char* str) {if (*str != '\0') {return 1 + my_strlen(str + 1);}return 0;
}
int main()
{int len = my_strlen("abc");printf("%d", len);return 0;
}

这里我们用来递归法来实现的，这里考虑到了地址的加1，很巧妙这个实现，然后每次用1+（）这个后面的值，就可以很方便的实现这个程序了，记住字符串很多都是用\0来作为限制条件的

四，迭代与递归的选择与二者之间的利与弊

什么时候用迭代法什么时候用递归法，我们可以拿斐波那契数列来举这个例子：

我们来用递归实现一下

#include<stdio.h>
int Fib(int n) {if (n <= 2) {return 1;}elsereturn Fib(n - 1) + Fib(n - 2);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d", ret);return 0;
}

这个是我们用递归法来实现的，但是用vs2019测试50的时候，很慢