Gentle Introduction to C : Recursion

Originally Posted on SeedBx

Welcome to the eight part of the Gentle Introduction to C series. As said before this series aims to provide you a brief introduction to C language.

In this post, we will be talking about the concept of recursion.

Recursion

Recursion is the process in which a function calls itself directly or indirectly and the corresponding function is called a recursive function.

Example :

void func() {

    // some code...

    func();

    // some code...

}

The above function func() calls itself in the function, so this is an instance when a function calls itself directly in a recursion.

void func1() {

    // some code...

    func2();

    // some code...

}

void func2() {

    // some code...

    func1();

    // some code...

}  

In the above code functions func1() and func2() calls itself, however unlike the previous code both the functions func1() and func2() calls itself indirectly.

Each recursion function consists of two parts :

1.    General (Recursive) Case: The part of the recursive functions which expresses the solution in terms of smaller version of itself.

2.    Base Case: The part of the recursive function for which the solution can be stated non-recursviely.

Let us understand about these parts through an example,

int fact(int n) {

    if(n==1)                // - (i)

        return 1;

    return n*fact(n-1);     // - (ii)

}

In the above program, a function fact() has been described which calculates the factorial of a given number. Here line -(i) is the base case where as line -(ii) is the general case.

Typically to solve a problem using recursion, we often try to break the problem statement in terms of smaller version/ inputs of the given statement and think of a base case for which the solution can be calculated easily.

Note : If the base case is not defined or not reached then a stack overflow error/ problem arises.

Example :

int fact(int n) {

    return n*fact(n-1);

}

The above function will never terminate and hence a stack overflow error occurs.

Memory Allocation to Different Function Calls

Whenever a function is called from main(), a portion of memory is allocated to it on the memory stack. So following the same pattern, whenever a recursive function calls itself a portion of the memory stack is allocated to that particular call on top of the previous call. This process continues until the base case is reached, after which the function calls are popped from the stack in a Last-In-First-Out (LIFO) manner.

For example, the call stack for fact(4) will be,

Note : Stack overflow error also occurs when a lot of function calls/ data are being pushed onto the stack, so that the total calls exceed the memory/ capacity of the stack.

Comparison with Iterative Method

The fact that every recursive solution has an iterative counterpart makes them direct candidates for comparison.

Example :

int fact(int n) {

    int res=1;

    for(int i=1;i<=n;i++)

    res=res*i;

    return res;

}

In the above code, fact() function described earlier is written in an iterative fashion.

Advantages of Recursion over Iteration

Recursive programs are often clean and easy to read and understand.

Disadvantages of Recursion over Iteration

·       Recursion requires higher space requirements as all the function calls remain in the memory stack until the base case is reached.

·       Recursion programs are slow, with respect to time, compared to their iterative counterparts due to all the function calls and returns overhead.

Recursion is a programming concept that is not only limited to C and expands to every programming language. Using recursion is one of the many ways to efficiently use computational powers to do difficult tasks and problems.

Thanks for reading.

Also See : Function, main() Function