More Recursion in C

Recursion is a repetitive process where a function calls itself directly or indirectly. A function is directly recursive when it calls itself from within its scope, and it is indirectly recursive when it calls other functions that eventually calls it back.

In general, we use two approaches to writing repetitive algorithms. The first approach is the iterative approach using loops, the other uses recursion.  For example, let’s consider a factorial:

factorial (n) = 1 if n = 0
                n * (n -1) * (n -2) ... 1 if n > 0

A repetitive function is iterative when the definition of the function involves only the parameters and not the function itself. A repetitive function is defined recursively whenever the function appears within the definition itself. To look at factorials again, we would define them as:

factorial(n) = 1 if n = 0
               n * factorial(n - 1) if n > 0

 

We will write two functions, one two solve the factorial problem in an iterative manner, and the other to solve the factorial problem in a recursive manner.

#include <stdio.h>
#include <stdlib.h>

long itFactorial(int n){
    int i;
    long rValue = 1;
    for(i = 1; i <= n; i++){
        rValue = rValue * i;
    }
    return rValue;
}

long recFactorial(int n){
    if(n==0) { return 1;}

    return n * recFactorial(n-1);

}

int main()
{

    printf("%li\n", itFactorial(7));

    printf("%li\n", recFactorial(7));

    return 0;
}

Recursive functions have two elements, solving one part of the problem, and/or reducing the size of the problem. The call that delivers a definitive solution is known as the base case. Every recursive function must have a base case.

When implementing a recursive function, we should bear in mind how the function’s arguments are put on the stack. The stack frame grows by push operations caused by function calls, and it shrinks by pop operations by function returns. Each call gets a fresh copy of automatic variables that are totally independent of the previous set of values.

A popular example of a recurrence relation is the Fibonacci sequence, in which a number is the sum of the previous two numbers. The first few numbers of the Fibonacci sequence are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. To start the sequence, we define the first two numbers as 0 and 1, so that the third number is also 1 (0 + 1), and the fourth number in the sequence is 2 (1 + 1).

We will see two examples of the recursive Fibonnaci function.

#include <stdlib.h>
#include <stdio.h>

int fibA(int iParam){
    int rValue;

    //base case for 0 and 1 in the sequence
    if(iParam == 0 || iParam == 1) { return iParam; }

    //calls itself twice
    rValue = fibA(iParam - 1) + fibA(iParam - 2);

    printf("Returning %d\t", rValue);

    return rValue;
}

int fibB(int iNum, int iPrevOne, int iPrevTwo){
    int rValue;

    if(iNum == 0){
        printf("iNum == 0, returning %d\n", iPrevTwo);
        return iPrevTwo;
    } else if (iNum == 1){
        //when count reaches 1, returning back the final number
        //reached by adding iPrevOne and iPrevTwo
        printf("iNum == 1, returning %d\n", iPrevOne);
        return iPrevOne;
    } else {
        printf("%d, %d, %d\n", iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        rValue = fibB(iNum-1, iPrevOne + iPrevTwo, iPrevOne);
        return rValue;
    }
}


int main()
{

    int i = 0;

    printf("\nfibA(5) = %d\n", fibA(5));
    printf("\nfibA(8) = %d\n", fibA(8));

    printf("\nfibB(7) = %d\n\n", fibB(7, 1, 0));
    printf("\nfibB(9) = %d\n", fibB(9, 1, 0));

    return 0;
}

We can also use a recursive function to find the greatest common denominator. The function will return the second parameter if the first parameter modulo the second parameter is 0, meaning that they divide evenly. Otherwise, the function will call itself, with the second parameter as the first argument, and the remainder of the modulo operation as the second argument.

#include <stdlib.h>
#include <stdio.h>

int findGCD(int a, int b){
    int remainder;
    if((remainder = a % b) == 0){
        return b;
    }
    return findGCD(b, remainder);
}


int main()
{
    printf("The GCD of 100 and 8 is %d\n", findGCD(100, 8));
    printf("The GCD of 150 and 5 is %d\n", findGCD(150, 5));

    return 0;
}

One of the most famous examples of a recursive s0lution is the Towers of Hanoi problem, but we will look at that at another time.

 

 

 

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s