[C语言]第十一节 函数递归一基础知识到高级技巧的全景探索

#include <stdio.h>
int main()
{
 printf("hehe\n");
 main();//main函数中⼜调⽤了main函数
 return 0;
}

#include <stdio.h>
int Fact(int n)
{

if (n == 0)
return 1;
else
return n * Fact(n - 1);
}
int main()
{
int n = 0;
scanf("%d", &n);
n = Fact( n);
printf("%d",n);
return 0;
}

Print(n)

如果 n 是 1234 ，那表⽰为

Print( 1234 ) // 打印 1234 的每⼀位

其中 1234 中的 4 可以通过 % 10 得到，那么

Print( 1234 ) 就可以拆分为两步：

1. Print( 1234 / 10 ) // 打印 123 的每⼀位

2. printf ( 1234 % 10 ) // 打印 4

完成上述 2 步，那就完成了 1234 每⼀位的打印

那么 Print( 123 ) ⼜可以拆分为 Print( 123 / 10 ) + printf ( 123 % 10 )

int Fact(int n)
{
 if(n==0)
     return 1;
 else
     return n*Fact(n-1);
}

int Fact(int n)
{
 int i = 0;
 int ret = 1;
 for(i=1; i<=n; i++)
 {
     ret *= i;
 }
 return ret;
}

上述代码是能够完成任务，并且效率是⽐递归的⽅式更好的。

事实上，我们看到的许多问题是以递归的形式进⾏解释的，这只是因为它⽐⾮递归的形式更加清晰， 但是这些问题的迭代实现往往⽐递归实现效率更⾼。

当⼀个问题⾮常复杂，难以使⽤迭代的⽅式实现时，此时递归实现的简洁性便可以补偿它所带来的运 ⾏时开销。

举例3：求第n个斐波那契数

我们也能举出更加极端的例⼦，就像计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契 数的问题通过是使⽤递归的形式描述的，如下：

#include <stdio.h>
int Fib(int n)
{
if (n <= 2)
return 1;
else
return Fib(n - 1) + Fib(n - 2);
}
int main()

{
int n = 0;
scanf("%d", &n);
n=Fib(n);
printf("%d", n);
return 0;
}

#include <stdio.h>
int count = 0;
int Fib(int n)
{
 if(n == 3)
 count++;//统计第3个斐波那契数被计算的次数
 if(n<=2)
     return 1;
 else
     return Fib(n-1)+Fib(n-2);
}
int main()
{
 int n = 0;
 scanf("%d", &n);
 int ret = Fib(n);
 printf("%d\n", ret); 
 printf("\ncount = %d\n", count);
 return 0;
}