Fibonacci recursive function

Question

The program below is intended to print the first 25 terms of the Fibonacci sequence with a recursive function. I got the output, but the problem is that the program is not halting and the values are going to negative values once they get to large.

#include <stdio.h>
int fibo(int, int, int);
int main()
{
    int s, c, i;
    s = 1;
    c = 0;
    i = 0;
    fibo(s, c, i);
}
int fibo(int s, int c, int i)
{
    for(i = 0; i <= 25; i++)
    {
        s = s + c;
        c = s - c;
        printf("%d\n", s);
        fibo(s, c, i);
    }
}

Expected output:

My output:

1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903
-1323752223
512559680
-811192543
-298632863
-1109825406
-1408458269
1776683621
368225352
2144908973
-1781832971
363076002
-1418756969
-1055680967
1820529360
764848393
-1709589543
-944741150
1640636603
695895453
-1958435240
-1262539787
1073992269
-188547518
885444751
...

change the datatype from int to long or something larger than an integer. technically Fibonacci will print up to 45 from recursion. after that you need dynamic programming to print the values. — Sahan Dissanayaka, Oct 12 '20 at 12:11
Please [edit] to tag with the correct programming language tag (apparently [tag:c]). In the absence of a language tag, your question will get very few views, and those who do view it might not know C. — tripleee, Oct 12 '20 at 12:27
per [fibonacci sequence](https://www.mathsisfun.com/numbers/fibonacci-sequence.html) the fibonacci sequence starts with: `0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...` Not what the question states as the fibonacci sequence. The rule for the fibonacci sequence is: xn = xn−1 + xn−2 — user3629249, Oct 12 '20 at 23:41
regarding; `for(i = 0; i <= 25; i++)` This loop will itterate 26 times, not 25. Suggest: `for(i = 0; i < 25; i++)` — user3629249, Oct 12 '20 at 23:49
the `for()` loop, with the recursion will 'nest' some 26! (factorial) times. Even if the numeric values did not overflow their contents the available 'stack' would be overflowed, resulting in a program crash — user3629249, Oct 12 '20 at 23:54
OT: for ease of readability and understanding (the compiler does not care) please use meaningful variable names. Names like `c' and 's' are meaningless, even in the current context — user3629249, Oct 12 '20 at 23:59
the signature of the `fibo()` function says that the function returns an `int`, but there is no statement inside the function to return anything. suggest the signature be: `void fibo( long long int, long long int, int )` — user3629249, Oct 13 '20 at 00:09

score 1 · Answer 1 · answered Oct 12 '20 at 12:46

There are two issues responsible for what you are seeing.

The first issue is the recursive call fibo(s,c,i); at the end of the for-loop in function fibo. Why did you make that recursive call? The for-loop itself does all the job, there is no need for recursion here. Just delete that line and everything should work properly.

The second issue is with integer overflow. Congratulations to you if this is your first time experimenting with it! The short explanation is that the C type int cannot represent all integers as we know them in mathematics; only a finite range of integers can be represented. The integers in the Fibonacci sequence quickly become quite large, and cannot be represented adequately using the int type. When an arithmetic operation like s+c would produce a result larger than the largest number that can be represented as an int, integer overflow happens. It is undefined behaviour. In most situations but not all, the actual behaviour is that integers "wrap around" so that largest_integer + 1 == smallest_integer and of course, smallest_integer is negative.

If you replace every occurrence of int with long long int in your program, you will be able to see a few more numbers in the sequence. But the numbers will still become too large after a while.

See also:

hey thanks for the support, the question is to print Fibonacci series with recursive function, thats why i have added the fibo function at the end of for loop. — Sai Yashwanth, Oct 12 '20 at 16:56

score 0 · Answer 2 · answered Oct 12 '20 at 17:07

The idea of this exercise is to use recursion instead of a loop.

It’s unclear what your three parameters are supposed to represent (s, c and i aren’t, maybe, the most informative variable names). But in general a non-naïve recursive Fibonacci implementation might look as follows:

int fib(int n, int prev, int curr) {
    if (n == 0) return prev;
    if (n == 1) return curr;
    return fib(n - 1, curr, curr + prev);
}

And to print the first 25 numbers:

int main(void) {
    for (int i = 0; i < 25; i++) {
        printf("fib(%d) = %d\n", i, fib(i, 0, 1));
    }
}

Note: This calculates intermediate results redundantly. Removing this redundancy requires calling printf inside the fib function. But you’d generally want to avoid mixing computation and IO, and the above is still efficient enough to not make this necessary.

Fibonacci recursive function

2 Answers2