浅学函数递归

前言

1. 递归

递归其实是⼀种解决问题的⽅法，在C语⾔中，递归就是函数⾃⼰调⽤⾃⼰。

递归的思想：

把⼀个⼤型复杂问题层层转化为⼀个与原问题相似，但规模较⼩的⼦问题来求解；直到⼦问题不能再

被拆分，递归就结束了。所以递归的思考⽅式就是把⼤事化⼩的过程。

2. 递归的限制条件

有2个必要条件：

• 递归存在限制条件，当满⾜这个限制条件的时候，递归便不再继续。

• 每次递归调⽤之后越来越接近这个限制条件。

递归举例1：

n的阶乘的公式： n！ = n ∗ (n − 1)!

那我们就可以写出函数Fact求n的阶乘，假设Fact(n)就是求n的阶乘，那么Fact(n-1)就是求n-1的阶

乘，函数如下：

int Fact(int n)
{
  if(n<=0)//这两个都是限制条件
  return 1;
  else
  return n*Fact(n-1);
}
#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);
  int ret = Fact(n);
  printf("%d\n", ret);
  return 0;
 }

案例2

顺序打印⼀个整数的每⼀位.

输⼊⼀个整数m，打印这个按照顺序打印整数的每⼀位。

n是超过1位数的话，就得拆分每⼀位

1234%10就能得到4，然后1234/10得到123，这就相当于去掉了4

然后继续对123%10，就得到了3，再除10去掉3，以此类推

不断的 %10 和 \10 操作，直到1234的每⼀位都得到；

但是这⾥有个问题就是得到的数字顺序是倒着的

但是我们有了灵感，我们发现其实⼀个数字的最低位是最容易得到的，通过%10就能得到

那我们假设想写⼀个函数Print来打印n的每⼀位，如下表⽰

用代码实现

void Print(int n)
{
  if(n>9)
  {
  Print(n/10);
  }
  printf("%d ", n%10);
}

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

例子：1 1 2 3 5…

前面两个数的和等于第三个

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的时候，需要很⻓时间才能算出结果，这个计算所花费的时间，是我们很难接受的，

这也说明递归的写法是⾮常低效的，那是为什么呢？

其实递归程序会不断的展开，在展开的过程中，我们很容易就能发现，在递归的过程中会有重复计算，⽽且递归层次越深，冗余计算就会越多。所以我们有时要注意选择，斐波那契数的计算，使⽤递归是⾮常不明智的，我们就得想迭代的⽅式解决。

如下：

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;
}

迭代的⽅式去实现这个代码，效率就要⾼出很多了。