本文共 3272 字，大约阅读时间需要 10 分钟。
1、递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。
2、非递归就是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。 3、非递归是从堆栈的角度来编写程序，速度快，但代码复杂。 递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。对于同一个问题，如果对速度要求不高，建议用递归方式。
1.递归和非递归分别实现求第n个斐波那契数。
首先对于斐波那契数序列：1 1 2 3 5 8 13 21 34… 从第三项开始，每一项都等于前两项之和。int count = 0; //计数计算多少次f1int Fabonaci(int n) //递归{ if (n == 1 || n == 2) { count++; //count计数，体会递归的耗时 return 1; } else { return Fabonaci(n - 1) + Fabonaci(n - 2); //第n个数的斐波那契等于前两个之和 问题不断化小 }}int main(){ printf("%d\n", Fabonaci(5)); printf("计算%d次f1\n",count); system("pause"); return 0;} int Fabonaci(int n) //非递归{ int f1 = 1; int f2 = 1; int f3 = 0; int i = 0; for (i = 3; i <= n; i++) { f3 = f2 + f1; //1（f1） 1（f2） 2（f3） 3 5 f1 = f2; f2 = f3; //1（f1） 2（f2） 3 （f3） 5 } return f3;}int main(){ printf("%d\n", Fabonaci(10)); system("pause"); return 0;} 2.递归和非递归分别实现strlen
strlen遇到\0停止，引用数组引进头文件<string.h> ，字符串的长度就是字符个数。#includeint count = 0;int MyStrlen1(char *str) //非递归{ //int count = 0; assert(str != NULL); //断言str传进来不为空 while (*str != '\0') { count++; str++; } return count;}int main(){ char str[] = "abcdef"; printf("%s\n", str); MyStrlen1(str); printf("%d\n", count); system("pause"); return 0;}
int MyStrlen(char *str) //递归{ if (*str == '\0') { return 0; } else { return 1 + MyStrlen(str + 1); }}int main(){ char str[] = "abcdef";// *str = "abcdef"; int len = MyStrlen(str); printf("%d\n", len); system("pause"); return 0;} 3.递归和非递归分别实现求n的阶乘
int Fac(int n)//5! = 5*4! 5*4*3!{ if (n == 1) { return 1; } else { return n*Fac(n - 1); }}int main(){ printf("%d", Fac(5)); system("pause"); return 0;} 4.递归实现n^k
int MyPow(int n, int k) //递归{ if (k == 0) { return 1; } else { return n*MyPow(n, k - 1); //n*n^k-1 = n^k }}int main(){ int res = MyPow(5,3); printf("%d\n",res); system("pause"); return 0;} 5.递归方式实现打印一个整数的每一位
void print(int n) //123 { if (n > 9) { print(n / 10); } printf("%d ", n % 10);}int main(){ print(123); system("pause"); return 0;} 6 写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
int DigitSum(int n){ if (n < 10) { return n; } else//14 123 { return DigitSum(n / 10) + n % 10; }}int main(){ int res = DigitSum(1729); printf("%d\n",res); system("pause"); return 0;} 递归的过程是***先递后归*** 1729 172 17 1为递过程 ； 1 7 2 9为归过程
7.编写一个函数 reverse_string(char * string)（递归实现）
void reverse_string(char *p) //递归{ int len = strlen(p); //不包括\0 char tmp = *p; *p = *(p + len - 1); *(p + len - 1) = '\0'; //保证字符串长度不变 if (strlen(p + 1) > 1) { reverse_string(p + 1); } *(p + len - 1) = tmp; // *p 和 *(p+len-1) 进行交换}int main(){ char str[] = "abcdef"; printf("%s\n", str); reverse_string(str); printf("%s\n", str); system("pause"); return 0;} void reverse_string(char *str) //非递归{ char *left = str; char *right = str + strlen(str) - 1; while (left < right) { char tmp = *left; *left = *right; *right = tmp; //交换 left++; right--; }}int main(){ char str[] = "abcdef"; printf("%s\n", str); reverse_string(str); printf("%s\n", str); system("pause"); return 0;} 转载地址：http://crjwi.baihongyu.com/