关于递归

学习折腾算法

创建时间:2018-05-30 00:00

字数:309

注意
1.普通写法
2.迭代法
3.尾递归

递归（Recursion）的两种优化方法

跳台阶问题

注意

递归在汇编层面来看，是一种特殊的循环。

平时解释递归，会说调用函数自己。其实实际执行时，当“调用自己”，就又重新分配了一块内存来保存相应数据，进行运算。

1.普通写法

int Fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    else
    {
        return Fibonacci(n - 2) + Fibonacci(n - 1);
    }
}

递归的缺点在于可能存在很多重复的操作，原因就不赘述了。一种优化方式就是避免这些重复的操作，用空间保存已计算的值，不再做重复的计算。

比较起递归的从后往前计算（要算 fn(n)，先算 fn(n-1)，fn(n-2)），这种方式是从前往后计算。

2.迭代法

int Fibonacci(int n){
  int sta[3] = {1,1,0};
  if(n < 2){
    return 1;
  }
  for(int i = 2; i <= n; i++){
    dp[2] = dp[0] + dp[1];
    dp[0] = dp[1];
    dp[1] = dp[2];
  }
  return dp[2];
}

3.尾递归

用函数式编程能简单实现.(用 kawa 时写过.)

ps:尾递归就相当于迭代法吧…

(let sum ((i 100))
    (if (= i 0) 0
        (+ (sum (- i 1)) i)))

function factorial(n, total) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5, 1) // 120