C语言中的递归探讨（中级）
练习1 : 接受一个整型值，按照顺序打印它的每一位 (画图讲解)
接受一个整型值（无符号），按照顺序打印它的每一位。
例如︰输入∶1234，输出1234.
要顺序打印它的每一位，就需要得到它的每一位，1234最容易得到的就是个位
1234 % 10 = 4
1234 / 10 = 123 % 10 = 3
123 / 10 = 12 % 10 = 2
12 / 10 = 1 % 10 = 1
1 / 10 = 0
#include<stdio.h> void print(int n) { if (n > 9) { print(n / 10); } printf("%d ", n % 10); } int main() { unsigned int num = 0; scanf("%d", &num);//1234 print(num);//打印1 2 3 4 return 0; //print(1234) //print(123) 4 //print(12) 3 4 //print(1) 2 3 4 // 1 2 3 4 //当（）里面的数字大于9的时候就拆分，小于9，为个位数的时候停止拆分，进行打印 }
比较上面两个递归函数，我们可以看到： 递归的两个必要条件
①存在限制条件，当满足这个限制条件的时候，递归便不再继续。
②每次递归调用之后越来越接近这个限制条件。
注意：这两个条件是必要条件，不是充分条件，也就是说递归函数一定满足这两个条件，但是满足这两个条件不一定是递归。
看下面这个例子：
按F10进行调试：
每一次函数的调用，都需要在栈区分配一定的空间，调用次数太多，栈空间不够分配（被耗干），导致栈溢出。
所以我们在写递归代码的时候，一定要注意以下几点：
1、不能死递归，要有跳出条件，每次递归逼近跳出条件
2、递归层层不能太深
练习 2∶ 求字符串的长度（画图讲解)
编写函数不允许创建临时变量，求字符串的长度。
如果调用临时变量：如果用strlen算：
使用递归如下⬇⬇⬇⬇⬇⬇
初步解题思路：用了临时变量count
#include<stdio.h> #include<string.h> //求字符串长度 int my_strlen(char* pr) { int count = 0; while (*pr != '\0') { count++; pr++; } return count; } int main() { char arr1[] = "bit"; //int len = strlen(arr1);//求字符串长度 int len = my_strlen(arr1); //arr1是数组，数组传参，传过去的不是整个数组，而是首元素的地址 printf("%d\n", len); return 0; }
这种方式虽然计算出字符串的长度，但是创建了一个临时变量count，现在使用递归的方式来实现：
int my_strlen(char* pr) { if (*pr != '\0') return 1 + my_strlen(pr + 1); else return 0; } //把大事化小 //my_strlen("bit") //1+my_strlen("it") //1+1+my_strlen("t") //1+1+1+my_strlen("\0") //1+1+1+0 = 3
画图详解：
练习3 ∶ 求n的阶乘
求n的阶乘。(不考虑溢出)
#include<stdio.h> #include<string.h> int Fun1(int x)//迭代（循环）实现 { int i = 0; int y = 1; for (i = 1; i <= x; i++) { y = y * i; } return y; } int Fun2(int x)//递归实现 { if (x > 1) return x * Fun2(x - 1); else return 1; } int main() { int n = 0; int ret = 0; printf("请输入一个数:>>\n"); scanf("%d", &n); //ret = Fun1(n);//循环的方式 ret = Fun2(n);//递归的方式 printf("%d的阶乘为：%d\n", n, ret); return 0; }
练习4 ∶ 求第n个斐波那契数 （不考虑溢出）
求第n个斐波那契数。（不考虑溢出）
介绍斐波那契数列，斐波那契数列的排列是：1 , 1，2，3，5，8，13，21，34，55，89，......
依次类推下去，你会发现，它后一个数等于前面两个数的和。
#include<stdio.h> int count = 0; int Fib1(int x)//递归实现 { if (x == 3) count++; if (x <= 2) return 1; else return Fib1(x - 1) + Fib1(x - 2); } int Fib2(int x)//函数实现 { int a = 1; int b = 1; int c = 1; while (x > 2) { c = a + b; a = b; b = c; x--; count++; } return c; } int main() { int n = 0; int ret = 0; scanf("%d", &n); //ret = Fib1(n);//求第n个斐波那契数 ret = Fib2(n);//循环实现 printf("%d\n", ret); printf("count = %d\n", count); return 0; }
我们在主函数里面写后续要被调用的某个函数的时候，先假设要用这个函数实现什么功能，直接去用，之后再去真正定义并实现这个函数。
这种思想叫做：TDD - 测试驱动开发 先去想函数怎么用，然后再实现。
递归结果：
递归方式：效率低
循环结果：
可以看出此时使用递归方式并不高效，其计算同一个数比如 3 的次数为 2 ^ n （递归方式）
而使用循环方式(n > 3时) 次数为 n
那我们如何改进呢 ?
在调试factorial函数的时候，如果你的参数比较大，那就会报错 : stack overflow(栈溢出）这样的信息。系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归)，这样有可能导致一直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。
那如何解决上述的问题 ？
1.将递归改写成非递归。
⒉使用static对象替代nonstatic局部对象。在递归函数设计中，可以使用static对象替代nonstatic局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放nonstatic对象的开销，而且static对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。
2、递归练习：
1、字符串逆序：
编写一个函数 reverse_string(char* string)（递归实现）
实现：将参数字符串中的字符反向排列，不是逆序打印。
要求：不能使用C函数库中的字符串操作函数。
比如 : char arr[] = “abcdef”，逆序之后数组的内容变成：fedcba
#include<stdio.h> //#include<string.h> //int my_strlen(char* str)//非递归方法求字符串长度 //{ // int count = 0; // while (*str != '\0') // { // count++; // str++; // } // return count; //} int my_strlen(char* str)//递归方法求字符串长度 { if (*str != '\0') return 1 + my_strlen(str + 1); else return 0; }上一篇： C语言（递归）使用递归方法，求解X^n