函数递归＋青蛙跳台阶——“C”

---

首先，我们先要知道一个问题，函数递归究竟是什么？ 

 程序调用自身的编程技巧称为递归（ recursion）。

 递归作为一种算法在程序设计语言中广泛应用。

 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解， 递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

 递归的主要思考方式在于：把大事化小

函数递归的两个必要条件：

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

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

---

下面，我们来看几个题目来更好地理解函数递归

接受一个整型值（无符号），按照顺序打印它的每一位。例如：1234，输出1 2 3 4

思考：我们肯定是要封装一个函数来实现此功能。

   1234=4

   1234/10=123

   123=3

   123/10=12

   12=2

   12/10=1

   1=1

 如果采用这种方式，我们可以很容易地就输出4 3 2 1，但是题目要求我们输出1 2 3 4

 我们可以这样：Print(1234)

                          Print(123) 4

                          Print(12) 3 4

                          Print(1) 2 3 4

下面，我们尝试写一下代码

1.  
   #include<stdio.h>
2.  
   void Print(unsigned int n)
3.  
   {
4.  
   if(n>9)//n是两位数以上的数字,才会拆分
5.  
   {
6.  
   Print(n/10);
7.  
   }
8.  
   printf("%d ",n%10);
9.  
   }
10.  
    int main()
11.  
    {
12.  
    unsigned int num=0;
13.  
    scanf("%u",&num);
14.  
    Print(num);
15.  
    return 0;
16.  
    }

 别看这段代码不长，但是想要很好地理解也是要花时间的

下面，我们来解释一下这段代码的意思：递归的意思是递推和回归

这段代码的意思我已经画图讲解地很清楚了，相信大家一看就明白

下面我们再来看一个题目

编写函数不允许创建临时变量，求字符串的长度 

在做这道题目之前，我们首先得知道有这样一个库函数strlen，是专门求字符串长度的

strlen统计的是\0之前出现的字符的个数

所以在做这道题目之前，我们先来做另一个题目：编写函数，求字符串的长度（模拟实现strlen）

1.  
   #include<stdio.h>
2.  
   int my_strlen(char *str)
3.  
   {
4.  
   int count=0;//计数器
5.  
   while(*str!='\0')
6.  
   {
7.  
   count ;
8.  
   str ;
9.  
   }
10.  
    return count;
11.  
    }
12.  
    int main()
13.  
    {
14.  
    char arr[10]="abcdef";
15.  
    //[a b c d e f \0 ]
16.  
    int len=my_strlen(arr);//数组名表示首元素的地址
17.  
    printf("%d\n",len);
18.  
    return 0;
19.  
    }

 这道题目我们是采用计数器的方法做的，下面我们再看看上面那道题目，采用递归的方式尝试一下

1.  
   #include<stdio.h>
2.  
   int my_strlen(char *str)
3.  
   {
4.  
   if(*str!='\0')
5.  
   {
6.  
   return 1 my_strlen(str 1);//使用这种方式不会改变str
7.  
   //尽量不使用 str，因为这样会改变str
8.  
   }
9.  
   else
10.  
    {
11.  
    return 0;
12.  
    }
13.  
    }
14.  
    int main()
15.  
    {
16.  
    char arr[10]="abcdef";
17.  
    int len=my_strlen(arr);
18.  
    printf("%d\n",len);
19.  
    return 0;
20.  
    }

 那么，为了更好地理解，我们还是采用画图的方式来看看

这个题目我们也就很好地讲清楚了

---

 递归与迭代

   求n的阶乘（不考虑溢出）

我们首先采用递归的方式来实现一下

1.  
   #include<stdio.h>
2.  
   int fac(int n)
3.  
   {
4.  
   if(n<=1)
5.  
   {
6.  
   return 1;
7.  
   }
8.  
   else
9.  
   {
10.  
    return n*fac(n-1);
11.  
    }
12.  
    }
13.  
    int main()
14.  
    {
15.  
    int n=0;
16.  
    scanf("%d",&n);
17.  
    int ret=fac(n);
18.  
    printf("%d\n",ret);
19.  
    return 0;
20.  
    }

 

 用递归的方式已经成功实现了，那么，我们来采用非递归的方式实现一下（也就是迭代）

1.  
   #include<stdio.h>
2.  
   int fac(int n)
3.  
   {
4.  
   int i=0;
5.  
   int ret=1;
6.  
   for(i=1;i<=n;i )
7.  
   {
8.  
   ret=ret*i;
9.  
   }
10.  
    return ret;
11.  
    }
12.  
    int main()
13.  
    {
14.  
    int n=0;
15.  
    scanf("%d",&n);
16.  
    int ret=fac(n);
17.  
    printf("%d\n",ret);
18.  
    return 0;
19.  
    }

 下面，我们再来看一个题目：求第n个斐波拉契数

 那首先，我们肯定要知道发斐波拉契数是个什么东西呀

  斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：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*）在现代物理、准晶体结构、化学等领域，斐波那契数列都有直接的应用，为此，美国数学会从 1963 年起出版了以《斐波那契数列季刊》为名的一份数学杂志，用于专门刊载这方面的研究成果。

 

哈哈哈，在学习C语言的过程中还可以学习数学，何乐而不为呢

 言归正传，我们来用代码实现一下

1.  
   #include<stdio.h>
2.  
   int fib(int n)
3.  
   {
4.  
   if(n<=2)
5.  
   {
6.  
   return 1;
7.  
   }
8.  
   else
9.  
   {
10.  
    return fib(n-1) fib(n-2);
11.  
    }
12.  
    }
13.  
    int main()
14.  
    {
15.  
    int n=0;
16.  
    scanf("%d",&n);
17.  
    int ret=fib(n);
18.  
    printf("%d\n",ret);
19.  
    return 0;
20.  
    }

 但是我们发现，用递归的方式求斐波拉契数，是有问题的

 我们会发现，并没有输出结果，那究竟是怎么回事呢？

  在使用 fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。

  使用 factorial 函数求10000的阶乘（不考虑结果的正确性），程序会崩溃。

  我们发现 fib 函数在调用的过程中很多计算其实在一直重复。

如果我们把代码修改一下：

1.  
   #include<stdio.h>
2.  
   int count=0;//全局变量
3.  
   int fib(int n)
4.  
   {
5.  
   if(n==3)
6.  
   {
7.  
   count ;
8.  
   //在计算第20个斐波拉契数时，第3个斐波拉契数被重复计算了多少次
9.  
   }
10.  
    if(n<=2)
11.  
    {
12.  
    return 1;
13.  
    }
14.  
    else
15.  
    {
16.  
    return fib(n-1) fib(n-2);
17.  
    }
18.  
    }
19.  
    int main()
20.  
    {
21.  
    int n=0;
22.  
    scanf("%d",&n);
23.  
    int ret=fib(n);
24.  
    printf("%d\n",ret);
25.  
    printf("\ncount=%d\n",count);
26.  
    return 0;
27.  
    }

我们会发现，才计算到第20个斐波拉契数，第3个斐波拉契数就已经被重复计算了这么多次，可见，做的无用功非常多 

那我们如何改进呢？

在调试 factorial 函数的时候，如果你的参数比较大，那就会报错： stack overflow（栈溢出）这样的信息。

系统分配给程序的栈空间是有限的，但是如果出现了死循环，或者（死递归），这样有可能导致一 直开辟栈空间，最终产生栈空间耗尽的情况，这样的现象我们称为栈溢出。

那如何解决上述的问题：

1. 将递归改写成非递归。

2. 使用static对象替代 nonstatic 局部对象。在递归函数设计中，可以使用 static 对象替代nonstatic 局部对象（即栈对象），这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销，而且 static 对象还可以保存递归调用的中间状态，并且可为各个调用层所访问。

那下面，用迭代的方式来实现一下求斐波拉契数

1.  
   #include<stdio.h>
2.  
   int fib(int n)
3.  
   {
4.  
   int a=1;
5.  
   int b=1;
6.  
   int c=1;
7.  
   while(n>=3)
8.  
   {
9.  
   c=a b;
10.  
    a=b;
11.  
    b=c;
12.  
    n--;
13.  
    }
14.  
    return c;
15.  
    }
16.  
    int main()
17.  
    {
18.  
    int n=0;
19.  
    scanf("%d",&n);
20.  
    int ret=fib(n);
21.  
    printf("%d ",ret);
22.  
    return 0;
23.  
    }

我们会发现，这样的方式也是非常ok的

提示：

1. 许多问题是以递归的形式进行解释的，这只是因为它比非递归的形式更为清晰。

2. 但是这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性稍微差些。

3. 当一个问题相当复杂，难以用迭代实现时，此时递归实现的简洁性便可以补偿它所带来的运行时开销。

---

接下来，我们来看一个函数递归的经典题目——青蛙跳台阶 

一只青蛙可以一次跳1级台阶或者一次跳2级台阶，例如：跳上第1级台阶只有一种跳法：直接跳1级即可。跳上2级台阶，有两种跳法：每次跳1级，跳2次；或者一次跳2级。问：跳上第n级台阶有多少种跳法？

设台阶数为N

当N=1时 只有一种跳法

当N=2时 可以跳两次一层，也可以跳一次两层，就有两种跳法

当N=3时 当有三层台阶时，青蛙可以选择先跳一层，剩下两层台阶，所以此时就是有两层台阶时                   的跳法，有两种：当青蛙选择第一次跳上两层台阶时，剩下一层台阶，此时有一层台阶                   时的跳法，所以三层台阶时的方法有：两层台阶的方法 一层台阶的方法

当N=4时 （1）先跳一层：若先跳一层，则剩下三层

                                         就是三层台阶的跳法

               （2）先跳两层：若先跳两层，则剩下两层

                                         就是两层台阶的跳法

                  结果就是：三层台阶的方法 两层台阶的方法

当N=n时 n层台阶的方法为：n-1层台阶的方法 n-2层台阶的方法

下面，我们来写代码

1.  
   #include<stdio.h>
2.  
   int frog(int n)
3.  
   {
4.  
   if(n==1)
5.  
   {
6.  
   return 1;
7.  
   }
8.  
   if(n==2)
9.  
   {
10.  
    return 2;
11.  
    }
12.  
    else
13.  
    {
14.  
    return frog(n-1) frog(n-2);
15.  
    }
16.  
    }
17.  
    int main()
18.  
    {
19.  
    int n=0;
20.  
    scanf("%d",&n);
21.  
    int ret=frog(n);
22.  
    printf("%d\n",ret);
23.  
    return 0;
24.  
    }

 下面，我们把题目修改一下

  让青蛙一次可以跳多个台阶（大于2）

首先我们让青蛙一次可以跳3个台阶

当N=1时 有一种跳法

当N=2时 有两种跳法

当N=3时 青蛙可以选择第一次先跳一层台阶或者两层台阶或者三层台阶，那么就有（1，1，1），               （1，2），（2，1），（3）四种方法

当N=4时 青蛙选择第一次跳一层台阶时，剩下三层台阶，则为N=3时的方法

               青蛙选择第一次跳两层台阶时，剩下两层台阶，则为N=2时的方法

               青蛙选择第一次跳三层台阶时，剩下一层台阶，则为N=1时的方法

 当N=4的所有方法为：N=3的所有方法 N=2的所有方法 N=1的所有方法

当N=n时 n层台阶的方法为：n-1层的所有方法 n-2层的所有方法 n-3层的所有方法

一样，我们下面还是来写代码

1.  
   #include<stdio.h>
2.  
   int frog(int n)
3.  
   {
4.  
   if(n==1)
5.  
   {
6.  
   return 1;
7.  
   }
8.  
   if(n==2)
9.  
   {
10.  
    return 2;
11.  
    }
12.  
    if(n==3)
13.  
    {
14.  
    return 4;
15.  
    }
16.  
    else
17.  
    {
18.  
    return frog(n-1) frog(n-2) frog(n-3);
19.  
    }
20.  
    }
21.  
    int main()
22.  
    {
23.  
    int n=0;
24.  
    scanf("%d",&n);
25.  
    int ret=frog(n);
26.  
    printf("%d\n",ret);
27.  
    return 0;
28.  
    }

                                   本质上，青蛙跳台阶问题就是斐波拉契数列问题                                    

---

好啦，小雅兰今天的内容就到这里了，今天终于写了一篇关于C语言的文章呀，花了小雅兰很多时间哟，未来也会继续加油呀，争取把C语言和C＋ 学好。

这篇好文章是转载于：学新通技术网