7.函数递归
7.1递归是什么？
递是推递的意思，归是回归的意思。
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式就是把大事化小。
7.2 递归的两个必要条件
1.存在限制条件，当满足这个限制条件时，递归便不再继续
2.每次递归调用之后越来越接近这个限制条件。
7.2.1 练习一 接受一个整型值（无符号）按顺序打印它的每一位
思路：
run代码：
#include <stdio.h> void print(int n) { if (n > 9) print(n/10); printf("%d ", n%10); } int main() { int n = 0; scanf("%d", &n); print(n); return 0; }
具体理解：
7.2.2 练习二 编写函数不允许创建临时变量，求字符串的长度
思路：
首先编写一个程序求字符串长度，再编写一个不创建临时变量的函数求字符串长度。求字符串首先想到用strlen库函数求；我们在想想可不可以用循环，当遇到不是’\0’的字符就用计数器加一，碰到’\0’时就结束循环；再想想，我们可以用递归的方法，每遇到一个不为’\0’的字符就加一，然后用指针指针指向下一个字符进行判断。思路循序渐进，一步一步推导让这个题目变得有头绪。
//假设这个字符串是"abc" //第一种方法用strlen库函数求解 #include <stdio.h> #include <string.h> int main() { char arr[] = "abc"; int num = strlen(arr); printf("%d\n", num); return 0; }
//假设这个字符串是"abc" //我们在想想可不可以用循环，当遇到不是'\0'的字符就用计数器加一，碰到'\0'时就结束循环 #include <stdio.h> int my_strlen(char *str) { //设置计数器 int count = 0; //然后实现函数功能 while (*str != '\0') { count++; str++; } return count; } int main() { char arr[] = "abc"; //求完长度后返回长度值 int len = my_strlen(arr); printf("%d\n", len); return 0; }
//利用递归的方法实现不创建临时变量求解字符串长度 ///<err>不是所有的控制路径都有返回值 </err> ///<reason>带返回值的函数最后并没有返回x，函数你没有提供足够的return 语句，有可能你是在某个循环或者条件控制语句中return了，但是你在函数内的右括号 “}”结束时并没有加多一条return 语句，那么这就是不正确的！所以在while循环语句后要对整体进行把控，返回一个值。</reason> #include <stdio.h> int my_strlen(const char* str) { while (*str != '\0') { return 1 + my_strlen(str + 1); } return 0;//必须添加，避免隐藏bug } int main() { char arr[] = "abc"; int len = my_strlen(arr); printf("%d\n", len); return 0; }
7.3 递归和迭代
7.3.1 练习一 求n的阶乘
思路：
当n<=1时，return 1;当n>1时，return nfactorial(n-1)
//递归 #include <stdio.h> int factorial(int x) { if (x <= 1) return 1; else return x * factorial(x - 1); } int main() { int n = 0; scanf("%d", &n); int mul = factorial(n); printf("%d\n", mul); return 0; }
这里有一个问题，就是当我们计算一个很大的数字的阶乘的时候，会产生很大的数，当这个数字超出存储的int类型（四个字节）的大小的时候，数据会丢失，也就出现栈溢出（stack overflow）的现象。
如何解决这个问题？
将递归改写为非递归
//迭代 #include <stdio.h> int factorial(int n) { int ret = 1; while (n>1) { ret *= n; n -= 1; } return ret; } int main() { int n = 0; scanf("%d", &n); int mul = factorial(n); printf("%d\n", mul); return 0; }
7.3.2 练习二 求第n个斐波那契数
思路：
当n<=2时，return 1;当n>2时，return fib(n-1)+fib(n-2)
//递归 //求第n个斐波那契数 //1 1 2 3 5 8 13 21 34 55... #include <stdio.h> fib(int x) { if (x <= 2) return 1; else return fib(x - 1) + fib(x - 2); } int main() { int n = 0; //输出第几个数字 scanf("%d", &n); int fib_number=fib(n); //数组这个斐波那契数 printf("%d\n", fib_number); return 0; }
这段代码有个问题，就是在我们计算第50个斐波那契数的时候特别浪费时间。
为什么浪费时间呢？看图：
有很多重复调用，我们来看看3这个数字被调用了多少次？
怎么解决这个问题呢？
将递归改写为非递归
//迭代 #include <stdio.h> int Fib(int n) { int a = 1; int b = 1; int c = 1; //a b c while (n>2) { c = a + b; a = b; b = c; n--; } return c; } int main() { int n = 0; scanf("%d", &n); int ret = Fib(n); printf("%d\n", ret); return 0; }
提示：
许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运时开销。
递归一定要有限制条件，不然就是死递归。
循环只是迭代的一种，可不能认为迭代就是循环。
递归会出现重复或者栈溢出问题，这时我们就要用迭代或者非递归形式去解决具体问题。
