Doubt in extracting the recursive Fibonacci recurrence equation

Question

Doubt in extracting the recursive Fibonacci recurrence equation

Navigation

#1 by (3 votes)
#2 by (3 votes)
#3 by (0 votes)

3

In some materials on the internet, I found this algorithm to extract the recurrence equation of the recursive factorial:

int qdr(int x, int n) {
   if(n == 0)
     return 1;
   else
     return x * qdr(x, n-1);
}

When n > 1 , the function does an operation that has constant time, multiplication, and makes a recursive call that has size n - 1 .

So the recurrence is:

T(n) = T(n-1) + 1
T(1) = 1

Does the above explanation apply to recursive Fibonacci?

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

In this case the recurrence equation would be:

T(0) = 0;
T(1) = 1;
T(n) = 1 + T(n-1) + T(n-2) (1 soma mais 2 chamadas recursivas?)

Would that be it? I ask because I researched everything on the internet and nowhere shows 1 + T(n-1) + T(n-2) and yes T(n-1) + T(n-2) . Can anyone tell me the right way and why? Thanks!

asked by anonymous 03.10.2016 / 16:15

3 answers

How to use the SelectedValue value of DropDownList? How to customize scroll bar in Chrome?

score 3 · Answer 1

Only one fix, you do not "find algorithm to extract the recurrence equation". You extract the recurrence equation from an algorithm.

"In order to analyze the consumption of time of a recursive algorithm is needed to resolve a recurrence A recurrence is an expression that gives the value of a function in terms of the "previous" values of the same function. "

Fibonacci series:

Fn = Fn-1 + Fn-2        n > 2, 
F0 = F1 = 1
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

Recursive Algorithm:

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

It is not efficient because:

Terms Fn-1 and Fn-2 are computed independently
Number of recursive calls = Fibonacci number!
Cost to calculate Fn
- Exponential!!!

Recursionisnotalwaysthebestsolution,evenwhenthemathematicaldefinitionoftheproblemisrecursive.

intFibIter(intn){inti,k,F;i=1;F=0;for(k=1;k<=n;k++){F+=i;i=F-i;}returnF;}

InthiscomplexityisO(n).

this link has an example of how you draw the equation of recurrence of Fibonacci.

score 3 · Answer 2

The Fibonnaci sequence is one where each term equals the sum of the two previous terms.

Now, if each term is the sum of the two previous ones, then:

T(n) = T(n-1) + T(n-2)

By the way, that's exactly what we got in the algorithm you gave:

return fib(n-1) + fib(n-2);

That is, the sum of the two previous terms. Therefore, the T(n) = 1 + T(n-1) + T(n-2) formula is simply wrong. This " 1 + " that is there should not exist.

Finally, T(0) = 0 and T(1) = 1 are the initial terms of the sequence. if (n<2) return n; is responsible for dealing with such cases.

The implementation of this by direct and simple recursion is not efficient . The reason is that when calculating T(n) , we have two recursive calls to T instead of just one (as in factorial). Thus, each recursive call to T opens two other recursive calls, and each of these two calls opens two more, and each opens two more, and the business ends up growing more or less exponentially (it just is not exactly exponential because the recursive sub-calls have different sizes, then the first one is heavier than the second).

The exponential time burst can be avoided by verifying that when computing T(n-1) , we also have to indirectly calculate T(n-2) in the process, so it is not necessary to calculate T(n-2) twice (one as part of T(n-1) and the other directly). So if we can reuse the T(n-2) calculation to calculate the T(n-1) , the number of calls would go to linear instead of exponential.

One way to fix the recursive algorithm is to cache previously computed values to avoid having to recompute them:

// Crie um array grande o suficiente e inicialize todas as posições com -1.
int cache[] = ...;

int fib(int n) {
    if (n < 2) return n;
    if (cache[n] == -1) cache[n] = fib(n - 1) + fib(n - 2);
    return cache[n];
}

Another efficient way would be to eliminate recursion, which has the advantage of not needing the cache. But hence the recurrence relation is no longer clearly visible in the resulting algorithm:

int fib(int n) {
    if (n < 2) return n;
    int a = 0, b = 1;
    for (int i = 1; i < n; i++) {
        int c = b;
        b = a + b;
        a = c;
    }
    return b;
}

score 0 · Answer 3

"In mathematical terms, the sequence is defined recursively by the formula below, the first term F1 = 1:

F n = F n − 1 + F n − 2

"

Source link

Yes, it is called 2 times recursively by mathematical definition.