算法中的递推算法

Dear 丶 2024-03-17 15:39 86阅读 0赞

## 递推算法 ##

给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。

递推算法是一种简单的算法，即通过已知条件，利用特定关系得出中间推论，直至得到结果的算法。 递推算法分为顺推和逆推两种。

相对于[递归][Link 1]算法,递推算法免除了数据进出栈的过程，也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值. 比如阶乘函数：f(n)=n\*f(n-1) 在f(3)的运算过程中,递归的数据流动过程如下: f(3)\{f(i)=f(i-1)\*i\}-->f(2)-->f(1)-->f(0)\{f(0)=1\}-->f(1)-->f(2)--f(3)\{f(3)=6\} 而递推如下: f(0)-->f(1)-->f(2)-->f(3) 由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推.但是递归作为比较基础的算法,它的作用不能忽视.所以,在把握这两种算法的时候应该特别注意。

## 顺推法 ##

所谓顺推法是从已知条件出发，逐步推算出要解决的问题的方法叫顺推。 如斐波拉契数列，设它的函数为f(n),已知f(1)=1，f(2)=1;f(n)=f(n-2)+f(n-1)(n>=3,n∈N)。则我们通过顺推可以知道,f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3……直至我们要求的解。

## 逆推法 ##

所谓逆推法从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为逆推。

## 递推算法的经典例子 ##

【案例】从原点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？

样例输入：N=2

样例输出：result=7

样例输入：N=3

样例输出：result=17

解题思路：要解决走N步共有多少种走法，我们在拿到题目的时候最直接的想法就是先画出当N=1、N=2、N=3。。。。。N=n时对应走法的图例，由简单到复杂、由特殊到一般的推理过程，找出规律获得解题的思路。在数学上，我们称为归纳法。如果用编程的方法来求解这样的推理题，我们把这样的求解思路（算法）称之为递推法。递推的精髓在于f（n）的结果一般由f(n-1)、f(n-2)…..f(n-k)的前k次结果推导出来。我们在解决这类递推问题时，难点就是如何从简单而特殊的案例，找到问题的一般规律，写出f（n）与f(n-1)、f(n-2)…..f(n-k)之间的关系表达式，从而得出求解的结果。在历年noip的复赛当中，参赛选手对于这类题目都有这样的感受，往往花费了大量的时间来分析题目的一般规律，写出f（n）的一般表达式，而编程实现可能只需要几分钟的时间。所以我们在平时训练的时候，对于这样的递推题目，就必须掌握如何分析问题，从特殊推导出一般的规律，写出想要的关系表达式，问题就迎刃而解了。下面是这道题解题的心得，供大家参考：

（1）当N=1时，绘出走法图

![d5a941db20f6a19ddaa02bb2705b20ab.bmp][]

（图1）共有3种不同的走法，也就是黑色线条的数量，即f(1)=3

（2）当N=2时，绘出走法图

![2d9b955d4181e2578c1353144d5a31df.bmp][]

（图2）共有7种不同的走法，也就是绿色线条的数量，即f(2)=7

（3）当N=3时，绘出走法图

![ed5564aeef009b884448e0e94be1ec52.bmp][]

（图3）共有17种不同的走法，也就是红色线条的数量，即f(3)=17

由此，我们不难看出，对于任何一个起点，最多可以走出3种走法，但最少必须走出2种走法。那么我们要求出f(n)，实际上转换为如果我们能够得到上一步即f（n-1）有多少个终点是有3种走法的，有多少个点有2种走法的，那么问题就解决了。

a. 上一步，即f（n-1）有多少个终点是有3种走法的。

![ab037c585ac170fd2a47f60b272c465c.bmp][]

对于N=3时，f(n-1)=f(2), 有3个点A、B、C可以走出3种不同走法的，这3个点是怎么得到的呢？它的存在与N值有没有必然的联系？如果我们能找到它与N之间的关系，问题也就解决了。有了这样的思路以后，我们不难找到这样的规律：如果f（n-2）存在，即上上步存在，那么从上上步出发的线路里面必然会有一条向上走的线路，而这条向上走的线路在到达f（n-1）之后， 向f（n）出发时也必然有左、上、右这三种走法，那么我们就得出了这样的结论：当f（n-2）存在时，f（n-2）的值实际上就等价于f（n-1）有多少个终点是有3种走法。

b. f（n-1）有多少个终点是有2种走法的

![cf6c5668ad810c4d0b472eab860688ef.bmp][]

对于N=3时，有4个点D、E、F、G可以走出2种不同走法的，这4个点又是怎么得到的呢？它与N值有什么联系呢？ 实际上我们在解决了上一个问题的时候，这个问题就变得相当容易了， f（n-1）减掉刚才有3种走法的点，剩下的点不就是只有2种走法了吗？即f（n-1）-f（n-2）。

c. 得出f（n）的一般关系式

f(n)=3\*f(n-2)+2\*(f(n-1)-f(n-2) ) (n>=3)

化简：

f(n)=2\*f(n-1)+f(n-2) (n>=3)

有一点需要补充的就是，任何递推题，都会有临界条件。当N=1时，f(n)=3;,当N=2时，f(n)=7,这些都可以看成是临界条件。只有当N>=3时，即上上步存在的情况下，就可以得出f(n)的一般通式：f(n)=2\*f(n-1)+f(n-2)

（本题还有其他的解法，同学们可以继续挖掘！）

【参考程序】

#include <stdio.h>   
    #include <windows.h>    
    int main()    
    {    
       int n;    
       int i;    
       int fn_1,fn_2;    
       printf("please input n=");    
       scanf("%d",&n); //输入任意n值    
       int fn=0;    
       if(n==1)    
         fn=3; //初始化当n=1和n=2时的临界条件    
       else if(n==2)    
         fn=7;    
       else{    
         fn_1=7;    
         fn_2=3;    
         for(i=3;i<=n;i++)    
         {    
            fn=2*fn_1+fn_2; //当n>=3时fn的通式    
            fn_2=fn_1;//更新fn_1和fn_2的值    
            fn_1=fn;    
         }    
       }    
       printf("一共有%d种走法！\n",fn);  //输出结果    
       return 0;    
    }

复制

## java递归算法分析 ##

递归算法分析：就是把复杂的问题分解为若干个相对简单的子问题，一直分解下去，直到子问题有答案为止，也就是说到了递推的出口。 递归算法要注意的两点： (1) 递归就是在方法里调用自己; (2) 在使用递归算法时，必须要有一个明确的递归结束条件，称为递归出口。 先看一个简单的例子，求从1加到5的和，代码如下：

package com.juziku;
    
    /**
    * 递归测试
    * @author sunlightcs
    * 2011-3-9
    * http://hi.juziku.com/sunlightcs/
    */
    public class RecursionTest {
        
        /**
         * 求从1加到n的和
         */
        public static int sum(int n){
            if(n == 1){
                return 1;
            }else{
                return n + sum(n-1);
            }
        }
        
        
        public static void main(String[] args) {
            System.out.println(sum(5));
        }
    }

复制

先分析一下执行的流程： n=5时，执行sum(5)方法，返回的结果为：5 + sum(4) n=4时，执行sum(4)方法，返回的结果为：4 + sum(3) n=3时，执行sum(3)方法，返回的结果为：3 + sum(2) n=2时，执行sum(2)方法，返回的结果为：2 + sum(1) n=1时，执行sum(1)方法，返回的结果为：1 再向上返回，依次执行： 2+1 3+(2+1) 4+(3+2+1) 5+(4+3+2+1) = 15 思路应该是这样的： 要知道从1加到5的和，先得知道从1加到4的和，即：5+sum(4) 要知道从1加到4的和，先得知道从1加到3的和，即：4+sum(3) 要知道从1加到3的和，先得知道从1加到2的和，即：3+sum(2) 要知道从1加到2的和，先得知道从1加到1的和，即：2+sum(1) 从而很容易看出，递归的出口为1也就是sum(1)的值为1 再看一个例子，求5的阶乘，代码如下：

package com.juziku;
    
    /**
    * 递归测试
    * @author sunlightcs
    * 2011-3-8
    * http://hi.juziku.com/sunlightcs/
    */
    public class RecursionTest {
    
        /**
         * 求n的阶乘
         */
        public static int multiply(int n) {
            if(n == 1){
                return 1;
            }else{
                return n * multiply(n - 1);
            }
        }
        
        
        public static void main(String[] args) {
            System.out.println(multiply(5));
        }
    }

复制

文章分享自：

[Link 1]: http://baike.so.com/doc/5725016.html
[d5a941db20f6a19ddaa02bb2705b20ab.bmp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/b1b51042ce8649ccbaa25134990f0606.png
[2d9b955d4181e2578c1353144d5a31df.bmp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8092fed9809f4ef88df0e4d9b41a7a79.png
[ed5564aeef009b884448e0e94be1ec52.bmp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/3b61d5762645479992932a6a57ba74b2.png
[ab037c585ac170fd2a47f60b272c465c.bmp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/8b30190be133460c8330affc77390760.png
[cf6c5668ad810c4d0b472eab860688ef.bmp]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/15/d991dab8753d47e396559b00ac1347d1.png