对于C语言函数递归的简单理解（新手入门必看!!!）

admin管理员组

文章数量:1794759

对于C语言函数递归的简单理解（新手入门必看!!!）

什么是函数递归？ 程序调用自身的编程技巧称为递归（recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接 调用自身的 一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略： 只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 递归的主要思考方式在于：把大事化小 递归顾名思义也可以这样理解：递送与回归。 这里引用站上一位大佬的话： 我觉得特别贴切 “递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。 　　 循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。”

再放一个通俗易懂的列子，帮助大家更好的理解递归：

我需要打开快递包装，于是买了个剪刀。但是剪刀也有包装，所以我又买了一个剪刀，这个剪刀上又有包装，所以我又买了个剪刀。。。 最后我没钱了，于是我用牙撕开了最后一个剪刀的包装，然后用这个剪刀打开了倒数第二个简单的包装，然后。。。最后用第一个剪刀打开了快递的包装，拿出了东西。 这个沙雕的过程就叫递归，递归必须要有停止条件（例子中是我把钱花完），要不然你就会拥有无数的剪刀，但又打不开快递（忘了目的系列）。 

下面放几个简单的程序来进行递归的理解与使用。 1.接受一个整型值（无符号），按照顺序打印它的每一位。 void print(unsigned int n) // n=1234 { if (n > 9) { print(n / 10); //123 12 1 } printf("%d ", n % 10); 1 2 3 4 } int main() { unsigned int num = 0; scanf("%u", &num); print(num); return 0; }

2.编写函数不允许创建临时变量，求字符串的长度。

int my_strlen(char* s) { if (*s != '\\0') { return 1 + my_strlen(s + 1); } else { return 0; } } int main() { char arr[10] = { "abcdaaaa" }; int len = my_strlen(arr); printf("%d\\n", len); return 0; }

3.求n的阶乘。

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; }

4.求斐波那契数列底n个数的值。

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); return 0; }

 5.字符串逆序（递归实现）【将参数字符串中的字符反向排列，不是逆序打印。】

思路：
	逆置字符串，循环的方式实现非常简单
	1. 给两个指针，left放在字符串左侧，right放在最后一个有效字符位置
	2. 交换两个指针位置上的字符
	3. left指针往后走，right指针往前走，只要两个指针没有相遇，继续2，两个指针相遇后，逆置结束

#include <stdio.h> void reverse_string(char* arr) { int len = strlen(arr); char tmp = *arr; *arr = *(arr + len - 1); *(arr + len - 1) = '\\0'; if (strlen(arr+1)>=2) reverse_string(arr + 1); *(arr + len - 1) = tmp; } /*或者不用指针表示： int my_string(char* str) { int count = 0; while (*str != '\\0') { count++; str++; } return count; } void reverse_string(char str[]) { int len = my_string(str); int tmp = str[0]; str[0] = str[len - 1]; str[len - 1] = '\\0'; if (my_string(str + 1) >= 2) { reverse_string(str + 1); } str[len - 1] = tmp; } */ int main() { char arr[] = { "abc" }; reverse_string(arr); printf("%s", arr); }

6.计算一个数的每位之和（递归实现)

#include <stdio.h> int DigitSum(int n) { if (n > 9) { return DigitSum(n / 10) + n % 10; } else return n; } int main() { int n = 0; scanf("%d", &n); int ret = DigitSum(n); printf("%d\\n", ret); }

7.递归实现n的k次方 

#include <stdio.h> int pow(int n, int k) { if (k == 0) return 1; else if (k >= 1) return n*pow(n, k - 1); } int main() { int n = 0; int k = 0; scanf("%d %d", &n, &k); int ret = pow(n, k); printf("%d\\n", ret); return 0; }

8.  求 1+2+3....+n 的值 。

#include <stdio.h> int sum(int n) { if (n == 1) return 1; // 出口 (必要的) else return (sum(n - 1) + n); //根据表达式 F(n)=f(n-1)+n 取等号后边式子 称为 递推关系式 } int main() { int n = 0; scanf("%d", &n); int ret = sum(n); printf("%d\\n", ret); /*int num = sum(100); printf("%d\\n", num);*/ return 0; }

9. 已知一个整形数组，求出前n项数字之和。

#include <stdio.h> int sum(int arr[], int n) { if (n == 0) return arr[0]; else return sum(arr, n - 1) + arr[n]; } int main() { int arr[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; int ret = sum(arr, 4); printf("%d\\n", ret); return 0; }

10.  求一个已知数组里面前n个数字里面的最大值 （下标为n计算）

#include <stdio.h> int max(int arr[], int n) { if (n == 0) return arr[0]; else if (max(arr, n - 1) > arr[n]) return max(arr, n - 1); else return arr[n]; } int main() { int arr[] = { 7, 4, 8, 6, 3, 2, 9, 11, 5 }; int n = 0; scanf("%d", &n); int ret = max(arr, n); printf("%d\\n", ret); return 0; }

11.  递归中的冒泡排序

void bubble(int arr[], int L, int R) { if (L < R) { int i = 0; for (i = L; i <= R - 1; i++) { if (arr[i] > arr[i + 1]) { int tmp = arr[i]; arr[i] = arr[i + 1]; arr[i + 1] = tmp; } } bubble(arr, L, R - 1); } } int main() { int i = 0; int arr[7] = { 7, 6, 5, 4, 3, 2, 1 }; bubble(arr, 0, 6); for (i = 0; i < 7; i++) { printf("%d ", arr[i]); } return 0; }

12.求两数最大公约数 

int gcd(int a, int b) { if (a%b == 0) return b; else { int r = 0; r = a%b; return gcd(b, r); } } int main() { int a = 0; int b = 0; scanf("%d %d", &a, &b); int ret = gcd(a, b); printf("%d\\n", ret); }

总结：

什么时候用递归:

1．当解决一个问题递归和非递归都可以使用，且没有明显问题。那就可以使用递归。

2．当解决一个问题递归写起来很简单，非递归比较复杂，且递归没有明显问题，那就用递归。

3.如果说用递归解决问题，写起来简单，但是有明显问题，那就不能使用递归。得写出非递归的方式来解决。

小tips :

 递归想的深入了，很容易被绕进去，这时我们就要记住“ 我们是懒懒的老和尚，计算机就是忙碌的小和尚，我们不要管他们。”  把它想成，在还没有到达递归函数出口位置时，在做重复的事情就可以了。既然是重复的事情就没有必要每一样都去验证了 。

本文标签： 递归必看函数新手入门语言