# 递归 #### 求1-100的和 ~~~ function sum(n){ if(n==1) return 1; return sum(n-1) + n; } ~~~ #### 13579...的和 ~~~ function foo(n){ if(n == 0) return 1; return foo(n-1) + 2; } ~~~ #### 斐波那契数列 这里有两个方法实现： 1. 递归 ~~~ function Fib(n) { return n < 2 ? n : (Fib(n - 1) + Fib(n - 2)); } ~~~ 2. 数组缓存 ~~~ var IterMemoFib = function () { var cache = [1, 1]; return function (n) { if (n >= cache.length) { for (var i = cache.length; i < n; i++) { cache[i] = cache[i - 2] + cache[i - 1]; } } return cache[n - 1]; } }(); ~~~ #### 跳台阶问题 > 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 ~~~ function jumpFloor(number) { // write code here if(number === 1){ return 1 } if(number === 2){ return 2 } else{ var result = [] result[1] =1; result[2] =2; for(var i =3;i<=number;i++){ result[i] = result[i-1]+ result[i-2] } return result[number] } } ~~~ 或： > 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 > 因为n级台阶，第一步有n种跳法：跳1级、跳2级、到跳n级 跳1级，剩下n-1级，则剩下跳法是f(n-1) 跳2级，剩下n-2级，则剩下跳法是f(n-2) 所以f(n)=f(n-1)+f(n-2)+...+f(1) 因为f(n-1)=f(n-2)+f(n-3)+...+f(1) 所以f(n)=2*f(n-1) ~~~ function jumpFloorII(number) { // write code here return Math.pow(2,number-1) } ~~~ #### 矩形覆盖 > 我们可以用2乘1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2乘1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ > 思路：f(n) = f(n-1)+f(n-2), f(1) = 1; f(2) = 2; ~~~ function rectCover(number) { // write code here if (number === 1) { return 1 } if (number === 2) { return 2 } else { var result = [0, 1, 2]; for (var i = 3; i <= number; i++) { result[i] = result[i - 1] + result[i - 2] } return result[number] } } ~~~