递归算法与动态规划算法是计算机程序设计、数据结构中常见算法。有些书籍教材中对递归算法与动态规划算法比较时，总是指出动态规划算法优于递归算法，在问题较为复杂时不建议使用递归算法。本文主要以在实际问题解决过程中对递归算法与动态规划算法进行比较，判断其时间复杂度。

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).