Linux C语言 27-递归

Linux C语言 27-递归

本节关键字：C语言 递归
相关C库函数：main、printf

什么是递归？

在C语言中，程序调用自身的编程技巧称为递归（recursion）。递归从字面上可以理解为“递去+归来”。

使用递归的优缺点

使用递归的目的就是实现代码量的简化。
优点：代码量少，递归策略只需要少量的代码就可以完成过次重复计算，大大减少了程序的代码量。
缺点：运行效率低，递归算法在运行效率上比普通的循环要低。

递归算法的使用示例

####递归示例一：十进制正整数转二进制数
题目：请使用C语言中的递归来实现十进制正整数转换为二进制数。

// 题目：请使用C语言中的递归来实现十进制正整数转换为二进制数。
#include <stdio.h>void toBinaryEx(int num)
{if (num == 0) // 终止条件return;toBinaryEx(num / 2);printf("%d", num%2);    
}void toBinary(int num)
{printf("the binary of %-4d is: ", num);toBinaryEx(num);printf("\n");
}int main(int argc, char *argv[])
{   int i;for (i=1; i<=20; i++)toBinary(i);return 0;
}/** 运行结果：
the binary of 1    is: 1
the binary of 2    is: 10
the binary of 3    is: 11
the binary of 4    is: 100
the binary of 5    is: 101
the binary of 6    is: 110
the binary of 7    is: 111
the binary of 8    is: 1000
the binary of 9    is: 1001
the binary of 10   is: 1010
the binary of 11   is: 1011
the binary of 12   is: 1100
the binary of 13   is: 1101
the binary of 14   is: 1110
the binary of 15   is: 1111
the binary of 16   is: 10000
the binary of 17   is: 10001
the binary of 18   is: 10010
the binary of 19   is: 10011
the binary of 20   is: 10100
*//** 解析示例：十进制正整数9转换为二进制数的实际运算过程
toBinary(9)                                    printf("%d", 9%2); 1toBinary(4)                            printf("%d", 4%2); 0toBinary(2)                    printf("%d", 2%2); 0toBinary(1)            printf("%d", 1%2);  1toBinary(0)    return
*/

递归示例二：求n的阶乘

题目：请使用C语言中的递归来实现十进制正整数的阶乘。

// 题目：请使用C语言中的递归来实现十进制正整数的阶乘。
#include <stdio.h>int factorial(int n)
{if (n <= 1)return 1;return n*factorial(n-1);
}
int main(int argc, char *argv[])
{   int i;for (i=1; i<=5; i++)printf("%d! = %d\n", i, factorial(i));return 0;
}/** 运行结果：
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
*/

递归示例三：斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，数列的具体内容如下：
0、1、1、2、3、5、8、13、21、34、…
数学递推表示：F(0)=0, F(1)=1, f(n)=F(n-1)+F(n-2) (n≥2, n∈N)
问题：求斐波那契数列的第n项。

// 问题：求斐波那契数列的第n项。
#include <stdio.h>int fibonacci(int n)
{if (n == 0)return 0;if (n <= 2)return 1;return fibonacci(n-1)+fibonacci(n-2);}
int main(int argc, char *argv[])
{   int i;for (i=0; i<=20; i++)printf("fibonacci(%d)=%d\n", i, fibonacci(i));return 0;
}/** 运行结果：
fibonacci(0)=0
fibonacci(1)=1
fibonacci(2)=1
fibonacci(3)=2
fibonacci(4)=3
fibonacci(5)=5
fibonacci(6)=8
fibonacci(7)=13
fibonacci(8)=21
fibonacci(9)=34
fibonacci(10)=55
fibonacci(11)=89
fibonacci(12)=144
fibonacci(13)=233
fibonacci(14)=377
fibonacci(15)=610
fibonacci(16)=987
fibonacci(17)=1597
fibonacci(18)=2584
fibonacci(19)=4181
fibonacci(20)=6765
*/