函数递归
程序调用自身的编程技巧称为递归（ recursion）。
递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接
调用自身的
一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，
递归策略
只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
递归的主要思考方式在于：把大事化小
递归的两个必要条件
存在限制条件，当满足这个限制条件的时候，递归便不再继续。
每次递归调用之后越来越接近这个限制条件。
习题1：接受一个整型值（无符号），按照顺序打印它的每一位。
#include<stdio.h> int fun(int a) { if (a > 9) { fun(a / 10); } printf("%d ", a%10); } int main() { int a = 1234; fun(a); return 0; }
习题1思路分析：
习题2：编写函数不允许创建临时变量，求字符串的长度。
#include<stdio.h> int fun(char * b) { if (*b != '\0') return 1 + fun(b + 1); else return 0; } int main() { char a[] ="abcdef"; printf("%d",fun(a)); return 0; }
习题三：用递归求n的阶乘。（不考虑溢出）
#include<stdio.h> int fun(int b) { if (b <= 1) return 1; else return b*fun(b-1); } int main() { int a =5; printf("%d",fun(a)); return 0; }
习题四：求第n个斐波那契数。（不考虑溢出）
#include<stdio.h> int fun(int b) { if (b <=2) return 1; else return fun(b-2)+fun(b-1); } int main() { int a =10; printf("%d",fun(a)); return 0; }
习题五：非递归方式实现斐波那契数
#include<stdio.h> int fun(int x) { int a = 1; int b = 1; int c = 1; while (x >= 3) //前俩个数都为 1 1 { c = a + b; a = b; b = c; x--; } return c; } int main() { int a =10; printf("%d",fun(a)); return 0; }
习题六：将参数字符串中的字符逆序打印。
要求：不能使用C函数库中的字符串操作函数。
比如:
#include<stdio.h> void fun(char *b) { if (*b != '\0') fun(b + 1); if (*b == '\0') { return; } printf("%c", *b); } int main() { char a[] ="abcdefg"; fun(a); return 0; }
习题六 方法二
int mystrlen(char *a) { int count = 0; while (*a != '\0') { a++; count++; } return count; } reverse_string(char a[], int left, int right) { char tmp; if(left < right) { tmp = a[left]; a[left] = a[right]; a[right] = tmp; reverse_string(a, left+1, right - 1); } } int main() { char a[] = "abc"; int left = 0; int len = mystrlen(a) - 1; reverse_string(a, left, len); printf("%s", a); return 0; }
习题六 改编：将参数字符串中的字符逆序且不适用库函数，不是逆序打印。
#include<stdio.h> int Strlen(char* a) { if (*a != '\0') return 1+Strlen(a + 1); else return 0; } int reverse_string(char* b) { char tmp = *b; int len = Strlen(b) - 1; *b = *(b + len); *(b + len)='\0'; if(strlen(b+1)>2) reverse_string(b + 1); *(b + len) = tmp; } int main() { char a[] = "abcde"; reverse_string(a); printf("%s", a); return 0; }
习题七：汉诺塔
把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘
若A上面有一个盘子，把A可直接移动到C
若A上面有俩个盘子，把A上的第一个盘子移动到B,底部盘子移动到C，再把B上的盘子移动到C
若A上有三个盘子，把第一个盘子移动到C,第二个盘子移动到B，再把C上的盘子移动到B，再把A底部的盘子移动到C，再把B上的第一个移动到A，再把B移动到C,把A移动到C
#include<stdio.h> void move(char A,char B) { printf("%c-%c ", A, B); //移动盘子的函数 } void Han(int a,char z,char x,char c) //a：盘子的个数 z：其实的柱子，x：经过x进行转移的柱子 c：目的柱子 { if (a == 1) { move(z, c); } else { Han(a - 1, z, c, x); //如果盘子个数大于1，则先通过第三个柱子把除底部最后一个盘子的其余盘子移动到第二个柱子 move(z,c); // 接着把第一个柱子上最后一个盘子，移动到C， Han(a - 1, x, z, c);// 把第二根柱子上的盘子，通过第一个柱子移动到第三跟柱子上 } } int main() { Han(1, 'A', 'B', 'C'); return 0; }
我们发现一个问题；当用递归的方式求斐波那契数时，当数字过大，此时程序会崩溃
此时程序不会打印，这是因为，求斐波那契数列时，每一个数会调用俩次函数，并开辟俩个空间，当空间全被用光而我们仍然在开辟空间时，此时程序会崩溃
那如何解决上述的问题：
1. 将递归改写成非递归。
2. 使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代
nonstatic 局部对象（即栈对象），这不
仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保
存递归调用的中间状态，并且可为
各个调用层所访问。
提示：
1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。
2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。
3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开
销。
