CODEWITHSUNDEEP
algorithmrecursionfibonacci
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Optimizing the Fibonacci sequence recursive function by making it a wrapper

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 ?

Upvotes: 2

Views: 1998

Answers (1)

Esoteric Screen Name
Esoteric Screen Name

Reputation: 6112

Here's an example implementation of an additive sequence calculation, where ti = ti-1 + ti-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 ti 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 t0 = 0 and t1 = 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.

Upvotes: 4

Related Questions