一.知识点
1.基本概念
程序调用自身的编程技巧称为递归（ recursion）。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的 一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解， 递归策略 只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。 递归的主要思考方式在于：把大事化小。
2.递归的两个必要条件
1.存在限制条件，当满足这个限制条件的时候，递归便不再继续。
2.每次递归调用之后越来越接近这个限制条件。
二.基本题目
1.计算一个数的每位之和(递归实现)
写一个递归函数DigitSum(n),输入一个非负整数，返回组成他的数字之和
代码:
int DigitSum(unsigned int n) { if (n > 9) { return DigitSum(n / 10) + n % 10; } else return n;//最后结束只剩个位，然后开始返回 } int main() { unsigned int n = 0; scanf("%u", &n); int ret=DigitSum(n); printf("ret=%d\n", ret); return 0; }
将%10 /10 再加和转化为递归形式.
2.递归实现n的k次方
double K_min(int n, int k) { //结束条件 //n*n^(k-1) if (k < 0) return K_min(n, 1 / K_min(n, -k));//这段挺有意思,是k为负数递归的实现 else if (k == 0) return 1; else return n * K_min(n, k - 1);//k为正数递归的实现 } int main() { int n, k; scanf("%d%d", &n, &k); double ret = K_min(n, k); printf("ret=%f\n", ret); return 0; }
请读者注意，递归的限制条件很重要，这时应该是最后一次递归然后开始返回.
3.正序打印一个数的每一位
void print(unsigned int n) { //大事化小，条件约束 if (n>9) { print(n/10); } //出来循环打印 printf("%d ", n%10); //print(1234) //print(123) 4 //print(12) 3 4 //print(1) 2 3 4 } int main() { unsigned int input = 0; scanf("%u", &input); print(input);//接受一个无符号整型，然后按照顺序打印 return 0; }
这个递归相对容易.
4.逆序打印一个数的每一位
void digit(unsigned int num) { if (num > 0) { printf("%d", num % 10); digit(num / 10); } } int main() { unsigned int num = 0; scanf("%u", &num); digit(num); return 0; }
这道题目还是很有意思的，它让笔者对递归有了更深的理解，原来笔者一直将打印放在if条件句外，但是在递归回归后会执行之后的命令，使得重复打印。重新设计打印在前面，就规避了这个问题。
5.不创建临时变量计算一个字符串的长度
//递归求解 //my_strlen("abc) //1+my-strlen("bc) //1+1+my_strlen(c) //1+1+1+my_strlen("") //1+1+1+0 int my_strlen(char* str) { if (*str != '\0') //灵性的添加了一个1使得代码活络了起来 return 1 + my_strlen(str+1);//++str和str+1不相同，会导致str改变 else return 0; } int main() { char arr[] = "abc"; int len = my_strlen(arr); printf("%d\n", len); return 0; }
6.递归计算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; }
