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

各位CSDN的uu们你们好呀今天小雅兰的内容终于要回到我们的C语言了在之前我写函数这篇博客的时候就讲过会把函数递归的内容单独拿出来然后呢当时是说下一篇博客就会更函数递归和青蛙跳台阶由于一系列原因呢我更了一段时间的高等数学的文章把函数递归的内容一直放置到现在我想着做事情怎么也得有始有终吧我怀着激动的心情就有了今天的这篇文章啦

---

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

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

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

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

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

函数递归的两个必要条件

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

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

---

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

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

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

   1234%10=4

   1234/10=123

   123%10=3

   123/10=12

   12%10=2

   12/10=1

   1%10=1

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

 我们可以这样Print(1234)

                          Print(123) 4

                          Print(12) 3 4

                          Print(1) 2 3 4

下面我们尝试写一下代码

#include<stdio.h>
void Print(unsigned int n)
{
   if(n>9)//n是两位数以上的数字,才会拆分
   {
     Print(n/10);
   }
   printf("%d ",n%10);
}
int main()
{
   unsigned int num=0;
   scanf("%u",&num);
   Print(num);
   return 0;
}

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

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

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

下面我们再来看一个题目

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

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

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

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

#include<stdio.h>
int my_strlen(char *str)
{
   int count=0;//计数器
   while(*str!='\0')
   {
      count++;
      str++;
   }
   return count;
}
int main()
{
   char arr[10]="abcdef";
   //[a b c d e f \0   ]
   int len=my_strlen(arr);//数组名表示首元素的地址
   printf("%d\n",len);
   return 0;
}

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

 

#include<stdio.h>
int my_strlen(char *str)
{
   if(*str!='\0')
   {
      return 1+my_strlen(str+1);//使用这种方式不会改变str
      //尽量不使用++str因为这样会改变str
   }
   else 
   {
      return 0;
   }
}
int main()
{
   char arr[10]="abcdef";
   int len=my_strlen(arr);
   printf("%d\n",len);
   return 0;
}

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

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

---

 递归与迭代

   求n的阶乘不考虑溢出

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

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

 

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

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

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

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

  斐波那契数列Fibonacci sequence又称黄金分割数列因数学家莱昂纳多·斐波那契Leonardo Fibonacci以兔子繁殖为例子而引入故又称为“兔子数列”指的是这样一个数列1、1、2、3、5、8、13、21、34、……在数学上斐波那契数列以如下被以递推的方法定义F(0)=0F(1)=1, F(n)=F(n - 1)+F(n - 2)n ≥ 2n ∈ N*在现代物理、准晶体结构、化学等领域斐波那契数列都有直接的应用为此美国数学会从 1963 年起出版了以《斐波那契数列季刊》为名的一份数学杂志用于专门刊载这方面的研究成果。

 

 

 

 

 

 

 

 

 

 

 

 

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

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

#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);
   int ret=fib(n);
   printf("%d\n",ret);
   return 0;
}

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

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

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

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

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

如果我们把代码修改一下

#include<stdio.h>
int count=0;//全局变量
int fib(int n)
{
   if(n==3)
   {
     count++;
     //在计算第20个斐波拉契数时第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;
}

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

那我们如何改进呢

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

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

那如何解决上述的问题

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

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

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

#include<stdio.h>
int fib(int n)
{
   int a=1;
   int b=1;
   int c=1;
   while(n>=3)
   {
      c=a+b;
      a=b;
      b=c;
      n--;
   }
   return c;
}
int main()
{
   int n=0;
   scanf("%d",&n);
   int ret=fib(n);
   printf("%d ",ret);
   return 0;
}

我们会发现这样的方式也是非常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层台阶的方法

下面我们来写代码

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

 下面我们把题目修改一下

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

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

当N=1时 有一种跳法

当N=2时 有两种跳法

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

当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层的所有方法

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

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

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

---

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