CODEWITHSUNDEEP
cfunctionrecursion
T.Malo
T.Malo

Reputation: 512

C clarification on recursive functions

Hello getting better at C everyday, this is a example problem out of my textbook that generates fibonacci numbers and shows recursive functions. The program works but I just don't understand how... Specifically in parts (looper % 5), the whole functionfib and what printf(", %8ld", fib(looper)); is doing. Is it like saying fib() do x amount of times. If this problem is not easy to explain then could someone show me a easier way to understand how recursive functions work other then "towers of hanoi" example. Thanks. NOTE: program is meant to handle up to 30 numbers others wise it starts to look ugly. 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

long fib (long num);

int main(void)
{
    int seriesSize;

    printf("This program will print out a Fibonacci series.\n");
    printf("How many many numers do you wnat? ");

    scanf_s("%d", &seriesSize);

    printf("First %d Fib numbers: \n", seriesSize);
    for (int looper = 0; looper < seriesSize; looper++)
    {
        if (looper % 5)
        {
            printf(", %8ld", fib(looper));
        }
        else
        {
            printf("\n%8ld", fib(looper));
        }
    }
    printf("\n");
    return 0;
}

long fib(long num)
{
    if (num == 0 || num == 1)
    {
        return num;
    }
    return (fib(num - 1) + fib(num - 2));
}

Upvotes: 1

Views: 153

Answers (1)

Chris McGrath
Chris McGrath

Reputation: 1936

The idea behind the long fib(long num) function is that it mirrors the natural definition of the fibonacci sequence in that it is defined in terms of itself. That is, fib(n) is defined by fib(n-1) and fib(n-2). For example, fib(5) is fib(4)+fib(3).

The textbook has written the function in a recursive manner as described above. Note that this is not the most efficient way to implement a fibonacci function but it does logically make sense.

To understand it, it pays to trace through its execution with an example input. Take fib(3) for example. The first if statement doesn't trigger because num is not 0 or 1. Thus, it works out what fib(2) and fib(1) are, and adds them together. We know what fib(1) does - it returns 1 in the first if statement. Trace through fib(2) in a similar manner and you'll see that it returns 1. Thus, fib(3) will return fib(2)+fib(1)=2. You can extend this further - take fib(4). It will return fib(3)+fib(2), which we know are 2 and 1, hence fib(4) = 3.

This approach can be taken for most recursive functions - think of it as creating new instances of the fib() function which continually creates until it "bottoms out" at an end case (num == 1 or num == 0, in this case), and returns back up, filling in the answers until you get back to the function you started with, with the answer.

Upvotes: 1

Related Questions