递归执行以及递归在解决跳台阶、变态跳台阶中的运用

57 阅读 0 评论 38 点赞

我是靠谱客的博主痴情朋友，最近开发中收集的这篇文章主要介绍递归执行以及递归在解决跳台阶、变态跳台阶中的运用，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

所谓递归，就是程序中不断地调用自身最后解决问题的一种方式。每次递归都需要内存空间储存变量，因此递归需要注意其层次（递归条件），如果递归层数多到一定程度就会发生内存不足的情况，同时递归必须存在跳出条件否则将使整个程序陷入无限循环。

通俗讲，递归就是把一个大的问题不断地缩小，直到能够在一定范围简单得到结果，然后再反向计算。可以将整个递归过程想象成一组俄罗斯套娃游戏。在这组套娃上，每一层套娃都写着“值为里面一层的2倍”，在这种情况下，单从外面根本无法求解，这时候就需要依次将套娃取出，得到里面一层的信息，一直重复。这时候前面提到的跳出条件就变得格外重要，如果没有这个跳出条件程序就会一直往下一层寻找，直到内存不足崩溃。跳出条件其实就是指最里面的一个套娃中必须有一个确定的数字。

按要求，最右边的小套娃必须是确定的值。例如n的求阶乘，这个问题中存在隐形的跳出条件--n==1时，1的阶乘等于1。在计算时f(n)=n*f(n-1);即如果我们知道n-1的阶乘，乘以n就得到n的阶乘....要想知道n=2阶乘则必须知道n==1的阶乘，n==1阶乘条件给出，反过来得出f(2),f(3)..........f(n-1),f(n);

阶乘的每层都会压栈，可以想象算法的压栈过程，求f(n),程序首先将f(n)压栈，为了求f(n)则要先求f(n-1),此时f(n-1)压栈，如此循环，栈最上层为f(1)(跳出条件)，得到确定值（跳出条件）则弹出f(1)得到f(2),弹出f（2）得到f(3).......弹出f(n-1)得到f(n).

int recursive(int val)
{
   if (val == 1)//跳出条件
       return val;
   return val*recursive(val - 1);
}

int main()
{
   int n;
   while (cin >> n)
   {
       int value = recursive(n);
       cout << "n!=" << value << endl;
   }
   return 0;
}

跳台阶问题：

一般跳台阶每次可以调一阶或者两阶，当有n阶时有多少种方案。

这个问题如果从第一阶开始考虑则很难得出结论，反向递归考虑则假设最后一跳刚好跳到第n阶，则最后一跳有两种情况：跳一阶和跳两阶，当跳一阶则之前刚好跳n-1阶，跳两阶则之前刚好跳n-2阶。f(n)=f(n-1)+f(n-2),得到了递归条件还需要跳出条件。该题中跳出条件有两个：第一次跳一次或者两次，f(1)=1,f(2)=2(两个一阶，一个两阶)

int recursive(int val)
{
   if (val <= 0)
       return 0;
   if (val == 1 || val == 2)
       return val;
   return recursive(val - 1) + recursive(val - 2);
}

int main()
{
   int n;
   while (cin >> n)
   {
       int value = recursive(n);
       cout << "f(n)=" << value << endl;
   }
   return 0;
}

变态跳台阶

变态跳台阶即一次可以跳任意阶。f(n)=f(n-1)+f(n-2)+......+f(n-(n-1))+f(n-n),由数学公式可以简化f(n)=2*f(n-1)

int recursive(int val)
{
   if (val <= 0)
       return 0;
   if (val == 1)
       return 1;

   return 2*recursive(val-1);
}

int main()
{
   int n;
   while (cin >> n)
   {
       int value = recursive(n);
       cout << "f(n)=" << value << endl;
   }
   return 0;
}