recursive vs iterative

[xxleyi]

A function is a pattern for the local evolution of a computational process.

There are two typical kinds of computational process:

• iterative process
  • linear iterative
• recursive process
  • linear recursive
  • tree recursive

下面是一个实例，对指数快速运算，分别实现递归和迭代求解。

题目来源于新加坡国立大学 SICP JS 版练习题：

In general, the technique of defining an invariant quantity that remains unchanged from state to state is a powerful way to think about the design of iterative algorithms.

// recursive process
function fast_expt(b, n) {
  return n === 0
          ? 1
          : is_even(n)
            ? square(fast_expt(b, n / 2))
            : b * fast_expt(b, n - 1);
}

// iterative process
function fast_expt(b, n) {
  function iter(a, b, count) {
    return count === 0
            ? a
            : is_even(count)
              ? iter(a, square(b), count / 2)
              : iter(a * b, b, count - 1);
  }
  return iter(1, b, n);
}

function is_even(x) {
  return x % 2 === 0;
}

function square (x) {
  return x * x;
}

仔细推敲递归和迭代有什么大的实际价值吗？

有，且非常之大。它能帮我们将计算过程可视化。

事实上，代码中函数嵌套调用所生成的计算过程和递归很类似。也就是说，递归式的计算过程并不是必须发生在同名函数自我调用的过程中。

在头脑中可视化代码所生成的计算过程的形状的能力，对于成为专家级程序员来说，异常关键。

The ability to visualize the consequences of the actions under consideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity.

To become experts, we must learn to visualize the processes generated by various types of functions. Only after we have developed such a skill can we learn to reliably construct programs that exhibit the desired behavior.

---

回顾：可视化计算过程的能力确实很重要，无论是递归还是迭代，亦或是异步和多线程，无一不是如此。