详解函数递归运用

  • 前言
    • 一、什么是递归
    • 二、递归运用的两个必要条件
    • 三、递归与迭代
  • 总结撒花

哈喽！各位CSDN的uu们，我是你的博客好友小梦，希望我的文章可以给您带来一定的帮助，话不多说，文章推上！欢迎大家在评论区唠嗑指正，觉得好的话别忘了一键三连哦！

前言

  哈喽各位友友们，我今天又学到了很多有趣的知识，现在迫不及待的想和大家分享一下！在学习C语言函数时，想必大家对函数递归这个模块的知识点还是感到比较玄妙的，我开始学函数递归的时候给我的感受就是它很奇妙，但是对它如何递？又如何归？的过程不是很了解。经过我这几天的刻苦学习，终于领悟到了它的精髓！本文的知识干货满满，千万不要错过哟！好啦，废话不多说，下面就带着大家学习函数递归的知识。

一、什么是递归

什么是递归呢❓简单来说，程序调用自身的编程技巧称为递归（recursion）。函数递归这种方法，通常把一个大型复杂的问题层层转化成一个与原问题相似的规模较小的问题来求解的递归策略。只需要少量的代码就可以描述出解题过程中所需要的大量的重复计算，大大减少了程序的代码量。递归的主要思考方式： 把大事化小，函数从哪里调用就返回到哪里。

二、递归运用的两个必要条件

1. 存在限制条件，当满足这个限制条件时，递归便不再继续。
2. 每次递归调用之后越来越接近这个限制条件。
看着文字，大家可能还是感到有些困惑，接下来我举几个例子帮助大家更好的了解函数递归的这两个条件。
例一：接受一个整型值（无符号），按照顺序打印它的每一位。
例如：输入1234，输出1 2 3 4
画图分析：

解题代码：

#define _CRT_SECURE_NO_WARNINGS 1#includevoid print(int n){if (n > 10){print(n / 10);}printf("%d ", n % 10);}int main(){int num = 1234;print(num);return 0;}

运行结果：

例二：
编写一个函数不允许创建临时变量，求字符串的长度
画图分析：

解题代码：

#define _CRT_SECURE_NO_WARNINGS 1#includeint  my_strlen(const char*str){if (*str == '\0'){return 0;}else{return my_strlen(str + 1) + 1;}}int main(){char arr[] = "abcd";int len = my_strlen(arr);printf("%d", len);return 0;}

运行结果：

看了上面的代码，比起你写的非递归方式是不是在代码量上有所减少呢。哎呀，忙活了一个多小时，终于分析整理出来啦，只要大家能够看懂，理解递归调用的精髓就值啦！
这里小小总结一下吧：首先要知道函数递归的两个必要条件，然后真正了解到核心思想：大事化小，函数从哪里调用就返回到哪里。

三、递归与迭代

虽然递归写出来可以减少代码量，但是它也有缺点。为什么这么说呢？接下来举一个经典的例子，大家就知道啦，废话不多讲，分析如下！
例子：求第n个斐波那切数（不考虑溢出问题）

画图分析：

解题代码：

#define _CRT_SECURE_NO_WARNINGS 1#includeint 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 num = fib(n);printf("第%d个斐波那契数为：%d", n, num);return 0;}

测试代码，看看第10个斐波那契数是否为55：

这个例子是不考虑溢出的情况，所以只针对例子来说的话是没毛病的，但是实际上它存在溢出的问题。如果利用递归的方法的话，求第50个菲波那切数程序会消耗特别多的时间。我亲测是十分钟左右才跑出来。当求第10000个斐波那契数的时候，程序会崩掉。为什么会这样呢？我发现，在fib函数调用的时候，有很多重复的运算。如下图可知，当求第50个斐波那契数时，关于44这个的展开就已经重复出现很多次了，一直画下去的话，可想而知有多少数字是被重复展开计算的！
画图分析：

因此，这里用非递归的方式来求解斐波那契数这个问题，效率更好，虽然递归代码看起来很少，但这里内部是进行很多运算的，很多重复的运算在里面，从而使栈溢出。
非递归的方法实现：
首选先定义三个变量，当n >= 2的时候，pre与next都是赋值为1，pre+next = resurt当n>2时，

画图分析：

非递归解题代码：

#define _CRT_SECURE_NO_WARNINGS 1#includeint fib(int n){int pre;int next = 1;int resurt = 1;while (n > 2){n -= 1;pre = next;next = resurt;resurt = pre + next;}return resurt;}int main(){int n = 0;scanf("%d", & n);int c = fib(n);printf("%d", c);}

总结撒花

  许多问题是已递归的形式所解释的，这只是因为它比非递归的形式更为清晰。但是，这些问题的迭代实现往往比递归实现的效率更高，虽然代码的可读性稍微差些。所以对于递归的使用，要看具体问题具体分析，不要死用递归来解题。本篇文章旨在带领大家学习函数递归的知识， 如果我写的有什么的不好之处或者不足之处，请在文章下方给出你宝贵的意见。如果觉得我写的好的话请点个赞赞和关注哦~