Optimizing the Fibonacci sequence recursive function by making it a wrapper

Question

There is an issue with the recursive definition of the fibonacci sequence when it comes to efficiency. It is defined as follows:

private fib(int n) {
    if(n < 2) return n;
    else return fib(n - 1) + fib(n-2);
}

Suppose we call fib(5). This makes 1 call to fib(4) , two calls to fib(3), three calls to fib(2), five calls to fib(1) and three calls to fib(0).

In his book

Programming Abstractions in Java by Eric Roberts

Roberts mentions that we can resolve this efficiency issue by realizing that the fibonacci sequence is just a special case of the additiveSequence(int n, int t0, int t1) method. Basically, the Fibonacci sequence is just an additive sequence that strictly begins with 0 and 1. There are an infinite number of sequences that match the recurrence relation expressed by Fibonacci.

The author resolves the efficiency issue as follows:

private int fib(int n) {
    return additiveSequence(n, 0, 1);
}

So my questions is, by making the fib sequence a wrapper for the more general additiveSequence method, are we really improving efficiency ? Wouldn't the implementation of additiveSequence have the same exact "problem" in terms of efficiency that fib had, given that it does follow the same exact reccurence relation ?

You have not defined how your additiveSequence is implemented. If it is implemented not efficiently, you will have efficiency problem. — Salvador Dali
@SalvadorDali The author does not supply an implementation. The author assumes that you already have a method called additiveSequence and that you are using that as the return statement of the fib method. This is why I am so confused. — Mutating Algorithm
Then it is most probably either not a good written book or you have not read it carefully. additiveSequence is not a universally well known method so I would not expect people to know it. And the complexity of the algorithm and even its validity depends on this method. — Salvador Dali
@SalvadorDali "The key insight you need is that the nth term in any additive sequence is simply the (n-1)st term in the additive sequence that begins one step further along" This is the only explanation given and to me even this is cryptic — Mutating Algorithm
this may not be your point, but there is an O(1) formula for the fib numbers: maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/… — user3235832

Esoteric Screen Name Esoteric Screen Name · Accepted Answer · 2016-04-07T22:41:02

Here's an example implementation of an additive sequence calculation, where t_i = t_i-1 + t_i-2:

int additiveSequence(int n, int t0, int t1) {
  if(n==0) return t0;
  if(n==1) return t1;
  return additiveSequence(n-1, t1, t0+t1);
}

This method returns the n-th value in the series. Work through some examples and you should be able to convince yourself that each t_i will be calculated only once. Compare that with your naively implemented fib method and you can see why this approach is much faster.

The Fibonacci series is this kind of additive sequence, with the starting conditions t₀ = 0 and t₁ = 1. There's nothing particularly special about it, other than the fact that the obvious way to code it is a poor one. The author's point, presumably, is that implementation makes a huge difference in processing time. It does not appear to be clearly explained, however.

Optimizing the Fibonacci sequence recursive function by making it a wrapper

1 Answers