递归和非递归

#递归和非递归| 来源: 网络整理| 查看: 265

1、递归就是函数调用函数本身，运行起来就是函数嵌套函数，层层嵌套，所以函数调用、参数堆栈都是不小的开销，但是程序简单。 2、非递归就是不断地对参数入栈、出栈，省去了函数层层展开、层层调用的开销。虽然参数出入栈次数多了，但是一般都开辟固定的足够大的内存来一次性开辟、重复使用。 3、非递归是从堆栈的角度来编写程序，速度快，但代码复杂。递归是从问题本身的逻辑角度来编写，虽然速度相对慢，但代码容易理解。

对于同一个问题，如果对速度要求不高，建议用递归方式。

递归和非递归分别实现求第n个斐波那契数。递归和非递归分别实现strlen递归和非递归分别实现求n的阶乘递归实现n^k递归方式实现打印一个整数的每一位写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和（例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19 ）编写一个函数 reverse_string(char * string)（递归实现）实现：将参数字符串中的字符反向排列。要求：不能使用C函数库中的字符串操作函数。

1.递归和非递归分别实现求第n个斐波那契数。首先对于斐波那契数序列：1 1 2 3 5 8 13 21 34… 从第三项开始，每一项都等于前两项之和。

int count = 0; //计数计算多少次f1 int 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 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; }

【本文地址】

递归和非递归

递归和非递归

今日新闻

推荐新闻