记录一道面试题-台阶问题

昨天去面试的时候，碰到一道面试题，当时没啥思路，下来之后，思考良久，并搜索了相关问题，得到了答案，特此记录一下。

题目

现在有一个n阶的台阶，每次爬一层或两层，请问一共有多少中爬法？

分析

每次上一层或者两层，那么在第N层台阶的时候，前一步要么是在N-1层，要么是在N-2层，那么有公式可以表示，ƒ(N) = ƒ(N-1) + ƒ(N-2)，是不是跟斐布拉切数列的公式有点像呢？没错，这道题可以用斐波拉切数列的递归的方法来做。

递归解决

function main(n) {
  if(n === 1) return 1
  if(n === 2) return 2
  return main(n-1) + main(n-2)
}