总结|递归很套娃怎么办（来，这篇文章带你快速领悟递归的奥义） c语言|c++|算法|递归算法

文章图片

文章目录

递归的定义和必要条件
初步了解
- 打印一个数的每一位
- 计算一个数的每位之和
- 计算一个数的阶乘
进阶探讨
- 二分查找法递归实现
- 递归实现字符串函数strlen
- 递归实现字符串逆序
总结

递归的定义和必要条件很多人提到递归就不由自主的想到了“套娃“二字，确实递归要函数一层一层地开辟，是非常绕的。那么想要领悟到递归的精髓我们就要先了解递归的定义和递归的必要条件。
定义：
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的主要思考方式在于：把大事化小
必要条件：
1、存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。
当我们理解递归存在的必要条件后，我们要开始实战了，通过具体的问题来使用递归来解决，这样才能快速掌握。毕竟实践是检验真理的唯一标准。
初步了解打印一个数的每一位递归方式实现打印一个整数的每一位，如1357，我们要打印出1 3 5 7这四个数。
我们就可以想到用取余和取模来分开数字，
1357 % 10 - - - - - - -7 得到数字7
1357 / 1 - - - - - - -135
135 % 10 - - - - - - 5 得到数字5
135 / 10 - - - - - - -13
13 % 10 - - - - - - - 3 得到数字3
13 / 10 - - - - - - - -1
1 % 10 - - - - - - - -1 得到数字1
代码如下：

#define _CRT_SECURE_NO_WARNINGS 1 #include void print(int sum) { if (sum >= 10) {print(sum / 10); } printf("%d ", sum % 10); }int main() { int sum = 0; printf("请输入一个数字："); scanf("%d",&sum); print(sum); printf("\n"); return 0; }

可能一些朋友看到这里还是有点不太理解，我画了函数递归开辟的形象图有助于理解，图片如下：

文章图片

上面的分析我们用到了递归的定义和必要条件，即递归存在限制条件，如我们的
if（sum>=10）在这个范围内就一直开辟函数递归，等不满足限制条件后再一层层地返回去。
运行结果如下：

文章图片

计算一个数的每位之和递归方式实现计算一个数的每位之和，如1234，计算出1+2+3+4=10。如2468，要计算出2+4+6+8=20。
这个和我们上面的打印一个数的每一位是类似的，异曲同工。我们也用取余和取模从而得到1 2 3 4这四个数字。我们先得到4，接着是3，然后再是2，最后数字1不满足限制条件就一层层返回直到结束。
代码如下：

#include int fun(int sum) { if (sum >= 10) {return sum % 10 + fun(sum / 10); } else {return sum; } } int main() { int sum = 0; printf("请输入一个数字："); scanf("%d",&sum); printf("%d ", fun(sum)); return 0; }

函数递归开辟流程图如下：

文章图片

程序运行结果：

文章图片

计算一个数的阶乘比如要计算5的阶乘，那就是5 * 4 * 3 * 2 * 1=120。
所以我们阔以大事化小，先得到数字5，然后是4，接着是3，再接着是2，最后是1，所以可以用递归来实现。我们只要把握住开辟下一个函数时传过去的数字自减1即可。
代码如下：

#include int fun(unsigned int sum) { if (sum > 1) {return sum * fun(sum - 1); } else {return 1; } } int main() { unsigned int sum = 0; printf("请输入一个数字："); scanf("%d",&sum); printf("阶乘为：%ld ", fun(sum)); return 0; }

函数递归开辟流程图如下：

文章图片

上面就是函数递归的真面目，递归是自己调用自己，但不是停留在一个函数上，而是一直开辟相同的函数，直到不能满足限制条件。

文章图片

进阶探讨二分查找法递归实现二分查找法也被称为折半法，主要不断缩小半个区域，一直找下去。
如在 1 2 3 4 5 6 7 8 9 10中找数字7，
发现7比5大，查找空间变为：6 7 8 9 10；
发现7比8小，查找空间变为：6 7 ；
发现7比6大，查找空间变为：7 ；
最后发现就是7，则找到了。

文章图片

所以思路就明白了，递归和非递归写法如下：
递归法：

#include //不带返回值写法void fun1(int* p, int left, int right,int k) { if (left <= right) {int mid = (left + right) / 2; if (k < p[mid]) {right = mid - 1; fun(p, left, right, k); } else if (k > p[mid]) {left = mid + 1; fun(p, left, right, k); } else {printf("找到了，下标是：%d\n",mid); } } else {printf("找不到\n"); } }//带有返回值写法 int fun(int* p, int left, int right, int k) { if (left <= right) {int mid = (left + right) / 2; if (k < p[mid]) {right = mid - 1; return fun(p, left, right, k); } else if (k > p[mid]) {left = mid + 1; return fun(p, left, right, k); } else {return 1; } } else {return 0; } }int main() { int arr[10] = { 98,0,1,2,3,4,5,6,7,8}; int k = 5; int left = 0; //把最后一个元素下标赋值给right int right = sizeof(arr) / sizeof(arr[0]) - 1; int ret = Binary_Search(arr, left, right, k); if (ret!=0) {printf("找到了\n"); } else {printf("找不到\n"); } return 0; }

非递归法：

// *****二分查找 #include int main() { int k = 88; //定义要找的数字 int arr[] = { 11,22,33,44,55,66,77,88,99,100}; int sz = sizeof(arr) / sizeof(arr[0]); int left = 0; int right = sz - 1; int mid = 0; while (left <= right) {mid = (left + right) / 2; if (arr[mid] > k) {right = mid - 1; } else if (arr[mid] < k) {left = mid + 1; } else {printf("找到了，下标为：%d \n",mid); break; } } if (right < left) {printf("找不到数字\n"); } return 0; }

递归实现字符串函数strlen 我们平常求字符串长度的时候，用的库函数就是strlen(),那我们也模拟实现一下。
代码如下：

#include //迭代方式 int my_strlen1(char* p) { int count = 0; while (*p != '\0') {count++; p++; } return count; }//递归方式 int my_strlen2(char* p) { if (*p != '\0') {return 1 + my_strlen2(p + 1); } else {return 0; } }int main() { char* p = "abcdefg"; int ret1 = my_strlen1(p); int ret2 = my_strlen2(p); printf("递归方式结果: %d \n",ret1); printf("迭代方式结果: %d \n", ret2); }

有兴趣的朋友也可以画一下递归函数的图片来分析分析，我这里就不放了哈。
程序执行结果：

文章图片

递归实现字符串逆序字符串逆序顾名思义就是把字符串给颠倒过来，比如 “abcdef” 变成 “fedcba” 。
我们设两个变量，最左边为 left ，右边为 right ，只要把左边和右边互换就可以了，
然后左边往右边移动，右边往左边移动直到变量 left大于 right 。
所以思路分析完毕，字符串逆序也是能够很好体现递归的例子，也是利用大事化小。
代码如下：

#include int my_strlen(char* p) { if (*p != '\0') {return 1 + my_strlen(p + 1); } else {return 0; } }//递归方式写法 int Reverse(char* p, int left, int right) { if (left > right) {return 0; } else {char tmp = p[left]; p[left] = p[right]; p[right] = tmp; return Reverse(p, left + 1, right - 1); } }//非递归写法 voidReverse2(char* p, int left, int right) { while (left < right) {char tmp = p[left]; p[left] = p[right]; p[right] = tmp; left++; right--; } }int main() { char arr[] = "abcdef"; int len = my_strlen(arr); int left = 0; int right = len - 1; Reverse(arr,left,right); printf("反转结果为：\n"); printf("%s",arr); printf("\n\n"); return 0; }

程序执行结果为：