递推和递归：一个自下而上，一个自上而下

解决问题的思路不同

递推和递归是常见的解决问题的思路，在很多算法中都会用到，例如DFS算法基于递归实现，动态规划算法基于递推实现。

递推是从上到下解决问题，如想知道一个国家有多少人，我们从村这个一个行政级别开始，依次向上汇报，最后到国这个级别就能知道一个国家有多少人

递归是从上到下解决问题，如想知道一个国家有多少人。国家发布命令让各个省上报各自的人数，各个省又发布命令让各自市上报各自的人数，依次类推，最后到达村这个级别，开始统计自己的人数（递推出口），统计完后逐级上报，最后到国这个级别就能知道一个国家有多少人

爬楼梯

题目地址：70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。