Introduction to Recursion in C

A function that calls itself is said to be recursive. Recursion allows something to be defined in terms of smaller instances of itself.

While most of us are comfortable with breaking down problems into smaller pieces using functions, data structures, or methods and classes, using one single function to solve a big problem is somewhat more daunting.

#include <stdio.h>

void simpleRecursion(int num){
    if(num > 0){
        simpleRecursion(num-2);
        printf("%d\t", num);
        simpleRecursion(num-1);
    }
}

int main(void){

    int i;
    for(i=0; i < 6; i++){
        printf("\nPassed the function %d:\n", i);
        simpleRecursion(i);
        putchar('\n');
    }

    return 0;

}

The simpleRecursion() function only prints output if the parameter is greater than zero, meaning that any value printed must be one or greater.

Our second example is simpler still, it in effect goes backward one by one. We will use it to print the ASCII table backwards.

#include <stdio.h>

void simpleRecursion2(int num){
    if(num < 127){
        printf("%2c", num);
    }
    if(num > 33){
        simpleRecursion2(num - 1);
    }
}

int main(void){

    //print ASCII characters backward
    simpleRecursion2(127);

    return 0;

}

Factorials are a common mathematical example of recursion. The factorial of a number n, written n!, is the product of all numbers from n to 1. While we could follow an iterative approach, we can also define n! as itself being the product of smaller factorials. In this case, n! = (n-1)!, with n(0)=1. In this case, n(0) = 1 is what is known as the terminating condition. This is the point at which the function returns a value rather than calling itself again.

#include <stdio.h>

int factorial(int n){

    if(n>1){
        //return a call to the same function
        return n*factorial(n-1);
    }

    //terminating conditions
    if((n==0)||(n==1)){
        return 1;
    }

    //error
    return 0;
}

int main(void){

    printf("%d! = %d\n", 5, factorial(5));
    printf("%d! = %d\n", 3, factorial(3));

    return 0;

}

Remember, every recursive function must have at least one terminating condition.

To understand recursion, it helps to have a rough idea of the way functions are executed in C. When a function is called, a block of storage is allocated on the stack to keep track of data associated with the call. This block of storage is called a stack frame. The stack frame remains on the stack until the function call terminates.

This next example will sum an integer with every positive integer below it.

#include <stdio.h>

int recursiveAdd(int n){

    printf("%d", n);
    
    if(n>1){
        printf(" + ");
        return n + recursiveAdd(n-1);
    }
    
    if(n==1){
        return n;
    }
    //error
    return 0;
}

int main(void){
    
    int i = 0;
    
    while(i++ <= 10){
        printf(" = %d\n", recursiveAdd(i));
    }
            
    return 0;
    
}

The initial call to the recursiveAdd() function placed one stack frame on the stack. If we say, for instance, that the function’s argument was 3, then the initial stack frame does not meet any of the terminating conditions of the function, so the recursiveAdd() function is called again, with the argument being set to the current parameter, being four, minus one. This continues, with each stack frame persisting on the stack, until we reach a terminating condition and that function returns a value, in this case 1. Once this function call returns a value to the function that called it, that function can then return a value to the function call that in turn called it. Finally, we reach the stack frame created by the initial function call, and it returns the final value to the main() function.

You can get a copy of my book on standard C at http://www.amazon.com/Big-Als-C-Standard-ebook/dp/B00A4JGE0M. I also have a book on Linux commands http://www.amazon.com/Big-Als-Linux-Fedora-CLI-ebook/dp/B00GI25V30/

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