Russian Dolls of Programming

Unwrapping Recursion in C

7 min readJan 8, 2023

Recursion is like Russian dolls, where each doll contains a smaller version of itself. It involves breaking a problem down into smaller, simpler subproblems and using their solutions to solve the original problem.

Ready to explore the exciting world of recursion? We’ll explain how it works and give you examples to help you understand it. We’ll also discuss its pros and cons, so you can decide if it’s the right approach for your projects. Whether you’re a beginner or an experienced programmer, this post has something for you. Let’s dive in!

Definition

Recursion is a technique in which a function calls itself repeatedly until a certain condition is met. It is a way of solving problems by breaking them down into smaller, simpler subproblems and then combining the solutions to those subproblems to find the solution to the original problem.

Recursion can be a powerful tool for solving problems and simplifying code, but it is important to ensure that the base case is properly defined to prevent the function from entering an infinite loop.

Syntax

To avoid an infinite loop, here’s the general syntax of recursion in C:

return_type function_name(arguments)
{
    /* base case */
    if (condition)
    {
        return (value);
    }
    /* recursive case */
    else
    {
        return (function_name(modified_arguments));
    }
}

A recursive function in C typically has two cases: a base case and a recursive case. The base case is a condition that stops the recursion, and the recursive case is the code that calls the function itself with modified arguments. Let’s look at an example to make it clearer.

Imagine you’re trying to count down from 10 to 1. One way to do this is to use a for loop that counts down from 10 to 1 in C:

#include <stdio.h>

int main(void) 
{
    for (int i = 10; i > 0; i--)
    {
        printf("%d\n", i);
    }
    return (0);
}

This code will print the numbers 10 through 1 on separate lines in descending order. It does this by starting i at 10 and decrementing it by 1 each iteration until it is no longer greater than 0.

Alternatively, here is an example of a recursive function that accomplishes the same results:

#include <stdio.h>

void count_down(int n)
{
    if (n > 0)
    {
        printf("%d\n", n);
        count_down(n - 1);
    }
}

int main(void) 
{
    count_down(10);
    return (0);
}

The count_down function has a base case defined by the if statement if (n > 0). If n is greater than 0, the function will execute the code inside the curly braces. When the base case is reached, the function stops and returns control to the caller.
The recursive case is defined by the code inside the curly braces. When the base case is not met, the function prints the value of n and then calls itself with a modified argument of n — 1. This creates a loop that allows the function to count down from the given number.
The main function starts the recursive process by calling the count_down function with an argument of 10. The function will modify n and call itself until the base case is reached, at which point it will return control to the main function. The output will be the numbers 10 through 1 on separate lines.

Implementation

Not quite understanding recursion yet? No worries! Here are some examples of common ways that recursion is implemented in C to help you get a better understanding of the concept:

Example 1: Factorials

This function calculates the factorial of a given number using recursion.

int factorial(int n)
{
    if (n == 1)
    {
        return (1);
    } 
    else
    {
        return (n * factorial(n-1));
    }
}

The base case is defined as if (n == 1), which means that the function will return 1 and stop calling itself when n is equal to 1.
The recursive case is defined as return n * factorial(n-1), which means that the function will multiply n by the result of calling itself with an argument of n-1.
This process continues until the base case is reached, at which point the function will return the final result.

Example 2: Fibonacci Numbers

This function calculates the nth number in the Fibonacci sequence using recursion.

int fibonacci(int n)
{
    if (n <= 1)
    {
        return (n);
    } 
    else
    {
        return (fibonacci(n-1) + fibonacci(n-2));
    }
}

The base case is defined as if (n <= 1), which means that the function will return n and stop calling itself when n is less than or equal to 1.
The recursive case is defined as return fibonacci(n-1) + fibonacci(n-2), which means that the function will return the result of adding the result of calling itself with an argument of n-1 to the result of calling itself with an argument of n-2.
This process continues until the base case is reached, at which point the function will return the final result.

Example 3: Palindrome Check

This function checks if a given string (str) is a palindrome (a word or phrase that is spelled the same forwards and backwards).

int is_palindrome(char str[], int l, int r)
{
    if (l == r)
    {
        return (1);
    }

    if (str[l] != str[r])
    {
        return (0);
    }

    if (l < r + 1)
    {
        return (is_palindrome(str, l+1, r-1));
    }
    return (1);
}

The base case is defined as if (l == r), which means that the function will return 1 and stop calling itself when the leftmost index (l) is equal to the rightmost index (r). This is because a single character is always considered a palindrome.
The recursive case is defined as three separate function calls with modified arguments. The first call checks if the character at the leftmost index (str[l]) is equal to the character at the rightmost index (str[r]). If they are not equal, the function returns 0 to indicate that the string is not a palindrome.
If they are equal, the second call checks if l is less than r+1. If it is, the function calls itself with modified arguments of str, l+1, and r-1 to check the next pair of characters.
This process continues until the base case is reached, at which point the function stops calling itself and returns 1 to indicate that the string is a palindrome.

Example 4: Tower of Hanoi

This function solves the Tower of Hanoi puzzle for a given number of disks (n).

void tower_of_hanoi(int n, char from_rod, char to_rod, char aux_rod)
{
    if (n == 1)
    {
        printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
        return;
    }
    
    tower_of_hanoi(n-1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
    tower_of_hanoi(n-1, aux_rod, to_rod, from_rod);
}

The base case is defined as if (n == 1), which means that the function will print the instructions for moving a single disk and stop calling itself when n is equal to 1.
The recursive case is defined as three function calls with modified arguments. The first call moves the top n-1 disks from the starting rod (from_rod) to the auxiliary rod (aux_rod), using the destination rod (to_rod) as the auxiliary.
The second call prints the instructions for moving the nth disk from the starting rod to the destination rod.
The third call moves the n-1 disks from the auxiliary rod to the destination rod, using the starting rod as the auxiliary.
This process continues until the base case is reached, at which point the function stops calling itself and returns control to the caller.

Pros and Cons of Recursion in C

Pros:

Recursion can be a very elegant and concise way of solving problems, as it allows us to break a complex problem down into smaller, simpler subproblems and then combine the solutions to those subproblems to find the solution to the original problem.
Recursion can be very easy to understand and read, especially for problems that are naturally recursive in nature.
Recursion can be very efficient, as it allows us to reuse code and avoid having to write multiple loops to solve a problem.

Cons:

Recursion can be slower than iterative solutions, as it requires the overhead of function calls and the creation of new stack frames.
Recursion can be more difficult to debug, as it involves a series of function calls and can be harder to trace through.
Recursion can be prone to infinite loops if the base case is not properly defined or if the function is not called correctly.

Thanks for reading our post on the exciting world of recursion in C! We hope you now have a better understanding of this powerful tool and how it can be used to simplify complex problems. Whether you’re a beginner or an experienced programmer, recursion can be a valuable addition to your toolkit. Just remember to always define a proper base case to avoid infinite loops. Happy coding!