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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
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;
c语言编写递归函数}
运⾏结果：
7.递归⽅式实现打印⼀个整数的每⼀位
#include <stdio.h>
#include <stdlib.h>
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
请按任意键继续. . .

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。