C语言 递归算法及简单递归练习总结

递归

：大师 L. Peter Deutsch 说过：To Iterate is Human, to Recurse, Divine.中文译为：人理解迭代，神理解递归。
简单理解：
递归：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门，你继续打开它。若干次之后，你打开面前的门后，发现只有一间屋子，没有门了。然后，你开始原路返回，每走回一间屋子，你数一次，走到入口的时候，你可以回答出你到底用这你把钥匙打开了几扇门。
　　 循环：你打开面前这扇门，看到屋里面还有一扇门。你走过去，发现手中的钥匙还可以打开它，你推开门，发现里面还有一扇门（若前面两扇门都一样，那么这扇门和前两扇门也一样；如果第二扇门比第一扇门小，那么这扇门也比第二扇门小，你继续打开这扇门，一直这样继续下去直到打开所有的门。但是，入口处的人始终等不到你回去告诉他答案。
　　
详细参考：添加链接描述

递归：函数调用自身的编程技巧
人理解迭代，神理解递归。毋庸置疑地，递归确实是一个奇妙的思维方式。
递归的两个必要条件
1、存在限制条件，当满足这个条件时，递归便不再继续。
2、每次递归调用之后越来越接近这个限制条件。

1.递归和非递归分别实现求第n个斐波那契数。

斐波纳契数列fibonacci,又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……
在数学上，斐波纳契数列以如下被以递归的方法定义：
//F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）。

递归实现斐波那契数C程序

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
int fibonacci(int n)
{if(n <= 2){return 1;}else{return fibonacci(n - 1) + fibonacci(n - 2);}
}
int main()
{int n;printf("请输入你想输出第几项的斐波那契数：\n");scanf("%d", &n);printf("%d\n", fibonacci(n));system("pause");return 0;
}

运行结果：

不用递归实现斐波那契数C程序

#define _CRT_SECURE_NO_WARNINGS
#include 
#include int fibonacci(int n)
{int result = 0;int a = 1;int b = 1;int i;if(n <= 2){return 1;}for(i = 3; i <= n; i++){result = a + b;a = b;b = result;}return result;
}
int main()
{int n;printf("请输入你想输出第几项的斐波那契数：\n");scanf("%d", &n);printf("%d\n", fibonacci(n));system("pause");return 0;
}

2.编写一个函数实现n^k，使用递归实现

//n^k相当于k次 n*n*...*n，函数传递两个参数，k用来判断返回，k自减！
#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
int power(int n, int k)
{if(k == 0){return 1;}if(k == 1){return n;}return n * power(n, k - 1);
}
int main()
{int n;int k;printf("请输入要打印的n的k次方：\n");scanf("%d %d", &n, &k);printf("%d\n", power(n, k));system("pause");return 0;
}

运行结果：

3. 写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和，
例如，调用DigitSum(1729)，则应该返回1+7+2+9，它的和是19

#include 
#include 
int DigitSum(int n)
{if(n == 0){return 0;}return n % 10 + DigitSum(n/10);
}
int main()
{printf("%d\n", DigitSum(1729));system("pause");return 0;
}

运行结果：
19
请按任意键继续. . .

4. 编写一个函数 reverse_string(char * string)（递归实现）
   实现：将参数字符串中的字符反向排列。
   要求：不能使用C函数库中的字符串操作函数。

#include 
#include 
void reverse_string(char * str)
//*str传递的是字符串首字符的地址（指向首地址的指针）
{if(*(++str) != '\0'){reverse_string(str);}printf("%c", *(str - 1));
}
int main()
{char* ch = "abcdefg";printf("翻转前的字符串：%s\n", ch);printf("翻转后的字符串：");reverse_string(ch);printf("\n");system("pause");return 0;
}

运行结果：

5.递归和非递归分别实现strlen

#include 
#include 
int Strlen(char* str)
{if(*str == '\0'){return 0;}return 1 + Strlen(str + 1);
}
int main()
{char* ch = "abcdefg";int len = Strlen(ch);printf("%d\n", len);system("pause");return 0;
}

运行结果：
7
请按任意键继续. . .

6.递归和非递归分别实现求n的阶乘

#define _CRT_SECURE_NO_WARNINGS
#include 
#include 
int Factor(int n)
{if( n <= 1){return 1;}return n * Factor(n - 1);
}
int main()
{int n;printf("请输入要计算的阶乘数：\n");scanf("%d", &n);printf("%d\n", Factor(n));system("pause");return 0;
}

运行结果：

7.递归方式实现打印一个整数的每一位

#include 
#include 
void Print(int a)
{if(a > 9){Print(a / 10);}printf("%d ", a % 10);
}
int main()
{int a = 123456789;Print(a);printf("\n");system("pause");return 0;
}

运行结果：
1 2 3 4 5 6 7 8 9
请按任意键继续. . .

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！