CODEWITHSUNDEEP
crecursionfibonacci
Sai Yashwanth
Sai Yashwanth

Reputation: 1

Fibonacci recursive function

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:

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

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
...

Upvotes: 0

Views: 188

Answers (2)

Konrad Rudolph
Konrad Rudolph

Reputation: 545518

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.

Upvotes: 0

Stef
Stef

Reputation: 15504

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:

Upvotes: 1

Related Questions