9.递归、循环

函数自己调用自己本身，或者在自己函数调用的下级函数中调用自己。所有的递归都可以用循环来实现

递归

// 递归
function sun(n) {
  if (n === 1) return 1
  return sun(n - 1) + n
}
sun(100)

// 循环
function sun1(n) {
  let a = 0
  while (n > 0) {
      a += n;
      n--
  }
  return a
}
sun1(100)

// 递归示例
const a = {
    id: 1,
    name: 'zs',
    children: [
        {
            id: 2,
            name: 'ls',
            children: [
                {
                    id: 3,
                    name: 'ww'
                }
            ]
        }
    ]
}
const fun = (arr) => {
    console.log('arr', arr)
    let idList = []
    const getId = (arr) => {
        arr.forEach((item) => {
            idList.push(item.id)
            if(item.children) {
                getId(item.children)
            }
        })
    }
    getId(arr)
    return idList
}
fun([a]) // [1, 2, 3]

斐波拉契数列

// 斐波拉契数列 1,1,2,3,5,8,13,21,34,55,89...求第 n 项
// 递归
function fib(n) {
  if (n === 1 || n === 2) return n - 1
  return fib(n - 1) + fib(n - 2)
}
fib(10)

// 循环
function fn(n) {
  var a = 0,
      b = 1,
      c = a + b;
  for (let i = 3; i < n; i++) {
      a = b;
      b = c;
      c = a + b;
  }
  return c
}
fn(10)

爬楼梯

假如楼梯有 n 个台阶，每次可以走 1 个或 2 个台阶，请问走完这 n 个台阶有几种走法

//递归
function climbStairs(n) {
  if (n == 1) return 1
  if (n == 2) return 2
  return climbStairs(n - 1) + climbStairs(n - 2)
}
climbStairs(3)

// 循环
function fn1(n) {
  if (n >= 2) return n
  if (first=1,second=2)
  var third=0;
  for(let i=3;i<=n;i++){
    third = first+second;
    first = second;
    second = third;
  }
  return third
}
fn1(3)