previous | start | next

## The Efficiency of Recursion

- A person would just write down the values as they were computed and add up the last two to get the next one; no sequence value would ever be computed twice.
- To imitate the pencil-and-paper process, you would write a loop to compute Fibonacci numbers.

  >     int fib(int n)
  >     {
  >        if (n <= 2) return 1;
  >        int fold = 1;
  >        int fold2 = 1;
  >        int fnew;
  >        for (int i = 3; i <= n; i++)
  >        {
  >           fnew = fold + fold2;
  >           fold2 = fold;
  >           fold = fnew;
  >        }
  >        return fnew;
  >     }

previous | start | next