Fibonacci sequence C problems

Question

I was solving the problem... But I don't know why it does when a number greater than 200 is entered, it becomes an infinite loop. I used the recursive function. And I also only can use this function. What should I do?

#include <stdio.h>
int f(int n){   
    if (n<=0) return 0;
    else if(n==1 || n==2) return 1; 
    else {
        return f(n-1)+f(n-2);
    }
}

int main()    
{   
   int n;
   scanf("%d", &n);
   printf("%d", f(n));
   return 0;
}

Actually, it's not an infinite loop, it's just a very, very long loop. Computing Fibonacci numbers is a classic example (probably *the* classic example) of when recursion should *not* be used (at least, not without [memoization](https://en.wikipedia.org/wiki/Memoization)). — Steve Summit, Jun 25 '21 at 19:31
For n=46, my computer (a decently fast, modern laptop) took over 10 seconds to (correctly) compute the value 1836311903. For n=200, I estimate it would have taken 9,203,321,947,172,577,060,265,858 years. — Steve Summit, Jun 25 '21 at 19:44
@SteveSummit Only the lifetime of a few billion universes. Are you in a rush? — Barmar, Jun 25 '21 at 19:59
*"I also only can use this function"* Not sure exactly what that means. Does it just mean that you have to use the function signature `int f(int n)`? Or is there more to it than that? — user3386109, Jun 25 '21 at 20:04

score 4 · Accepted Answer · answered Jun 25 '21 at 19:37

… it becomes an infinite loop.

If you are judging whether the program is in an infinite loop by waiting for it to finish, you cannot distinguish between it being in a very long loop and it being in an infinite loop unless you wait forever, which I doubt you have done.

When you ask for f(200), the call to f evaluates f(199) and f(198). Then the first of those calls to f evaluates f(198) and f(197), and the second evaluates f(197) and f(196). When you follow this tree of calls, there are very roughly 10⁴¹ calls involved. So your program never terminates while you are waiting because evaluating that many calls would take eons.

(The number of calls for a given input n is going to be very similar to the Fibonacci sequence for n, and the ratios between numbers approaches (1+sqrt(5))/2, so the number of calls will be around (1+sqrt(5)/2)ⁿ times some constant depending on the initial terms.)

Fibonacci sequence C problems

1 Answers1