简单了解函数递归

一 了解函数递归

首先，我们通过一个简单的代码来理解函数递归。

#include<stdio.h>
int Func()
{return Func(n+1);
}
int main()
{int n = 5;Func(n);return 0;
}

这个就是函数递归，简单来说就是函数自己调用自己。

二 深入理解函数递归的思想

下面，以求n的阶乘为例，来更加深入的了解函数递归。

n的阶乘就是1~n的数字累积相乘,我们知道n的阶乘的公式：n！ = n ∗ (n − 1)! ,回归到这个公式的本来的推导过程，

也就是n!—>n*(n-1)!
(n-1)!—>(n-1)*(n-2)!
……
直到n是1或者0时，不再拆解
再稍微分析⼀下，当 n<=1 的时候，n的阶乘是1，其余n的阶乘都是可以通过上述公式计算。
n的阶乘的递归公式如下：

部分代码如下：

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

测试代码：

#include <stdio.h>
int Fact(int n)
{if(n<=0)return 1;elsereturn n*Fact(n-1);
}
int main()
{int n = 0;scanf("%d", &n);int ret = Fact(n);printf("%d\n", ret);return 0;
}

运行结果：
画图推演：

在求n的乘方的推导过程中，我们发现，这样的思路就是把⼀个较⼤的问题，转换为⼀个与原问题相似，但规模较⼩的问题来求解的，也就是递归的大事化小思想。
另外，函数递归是有限制条件的，对于求n的阶乘这个问题，我们发现它的限制条件是n是1或者0时，不再拆解，并且递归的过程，n在不断的趋近1或0。

三 函数递归的优缺点

对于递归，其好处就是用少量的代码解决复杂的问题，如果以迭代的方式解决这个问题，我们会感觉代码量明显增加。

#include<stdio.h>
int main()
{int n = 0;scanf("%d", &n);int ret = 1;if (n <= 1){ret = 1;printf("%d\n", ret);}else{for (int i = 2; i <= n; i++){ret *= i;}printf("%d\n", ret);}return 0;
}

但这并不是说递归就一定是好的，递归中，只要有函数调用，就会分配空间，递归会消耗一定的空间，还要注意递归是否栈溢出（stackoverflow)。
我们也能举出更加极端的例⼦，就像计算第n个斐波那契数，是不适合使⽤递归求解的，但是斐波那契数的问题通过是使⽤递归的形式描述的，如下：

看到这公式，很容易诱导我们将代码写成递归的形式，如下所⽰：

int Fib(int n){if(n<=2)       return 1;  else      return Fib(n-1)+Fib(n-2);
}
#include <stdio.h>
int main()
{int n = 0;scanf("%d", &n);int ret = Fib(n);printf("%d\n", ret); return 0;
}

可是，当我们n输⼊为50的时候，需要很⻓时间才能算出结果，这个计算所花费的时间，是我们很难接受的，这也说明递归的写法是⾮常低效的，那是为什么呢？

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计
算，⽽且递归层次越深，冗余计算就会越多。

我们可以作业测试：

#include <stdio.h>
int count = 0;
int Fib(int n)
{if(n == 3)count++;//统计第3个斐波那契数被计算的次数 if(n<=2)return 1;elsereturn 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;
}

输出结果：

那我们换成迭代的方式，我们知道斐波那契数的前2个数都1，然后前2个数相加就是第3个数，那么我们从前往后，从⼩到⼤计算就⾏了。

int Fib(int n)
{int a = 1;int b = 1;int c = 1;while(n>2){c = a+b;a = b;b = c;n--;}return c;
}

迭代的⽅式去实现这个代码，效率就要⾼出很多了。
通过这个例子，可以看出，有时候，递归虽好，但是也会引⼊⼀些问题，所以我们要分辨什么时候是用递归好，什么时候是用迭代好。

小结：函数递归，博主只给你们展示了它其中的冰山一角，剩下的博主还会继续分享的。