递回算法与动态规划算法是计算机程式设计、资料结构中常见算法。有些书籍教材中对递回算法与动态规划算法比较时，总是指出动态规划算法优于递回算法，在问题较为复杂时不建议使用递回算法。本文主要以在实际问题解决过程中对递回算法与动态规划算法进行比较，判断其时间复杂度。
计算机程式算法分析
1、问题
假设某人爬楼梯，一次只能攀爬1台阶或者2台阶，某楼梯共有N阶，请计算该人爬上N阶楼梯一共有多少种方法？2、递回算法
该问题与斐波那契数列十分类似，是一道地地道道的递回题目，因此可以直接使用递回算法实现问题求解。编写函式如下：
爬楼梯问题递回算法
3、动态规划算法
解决爬楼梯问题采用动态规划算法则可以从1层开始，计算到N层每层能够到达的方法，设计a，b两变数时刻表示到达每一层K前的两层，a是到达k-2层的方法，b是到达k-1层的方法。则可编写函式实现问题求解。函式定义如下：
爬楼梯问题动态规划算法求解
以上给出爬楼梯问题动态规划与递回算法求解函式，其中f(n)是用递回实现， v(n)是用动态规划实现。以台阶数为10，呼叫函式执行，可获取以下结果。
计算结果
如上图结果所示，当楼梯数量为10时，分别计算方法总数为89.为研究两种算法时间复杂度，我们在函式外部分别定义全域性函式 count1和count2,为计数器，在两个函式内部执行++运算。如图：
设定计数变数之后，继续呼叫两函式计算爬楼方法，当N=20时可以获取以下结果：
函式呼叫执行次数
由此可见，使用动态规划与递回算法执行问题求解过程N=20时，两函式呼叫次数差距较大，其中动态规划执行18次，递回算法执行了13529次。有兴趣读者可以自己尝试一下当N=50时可能递回算法将会导致浏览器卡死。因此在解决这个问题方面动态规划时间复杂度较低，仅为O(n),递回算法时间复杂度为O(2^n).
本头条号长期关注于青少年程式设计资讯分享；程式设计课程、素材、程式码分享及青少年程式设计培训。如果您对以上方面有兴趣，可关注该头条号，如有程式设计学习问题可以联络作者，共同探讨。
