Get started with Recursion

What a Recursive Function is and how to use it with the C programming language.

photo by Lode’s Computer Graphics Tutorial

This article will explain what a recursive function is and how to use it with the C programming language.

What is recursion?

In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. Wikipedia

Why use recursion?

Recursive thinking is essential in programming. It aids in the reduction of complex problems to simple solutions. It is a simpler alternative to loops in the code, making it easier to read and maintain. Recursive functions can frequently achieve the same result with less code than iterative solutions.

Example recursive functions

photo by geeksforgeeks.org

Recursion has two features.

1. Recursive Call

The function calls itself during execution. Each recursive call should solve a smaller instance of the same problem.

1. End condition (the base case)

To prevent calling itself infinity, there must be a condition known as the base case. When the condition is satisfied, the function stops calling itself and returns a specific value.

loop vs recursion

Let’s examine how to apply recursive functions and loops to the same problem.

How to find the factorial of 5 (5!)

Using while loop

#include<stdio.h>

int find_factorial(int n);

int main()
{
    printf("%d\n",find_factorial(5));
    return 0;
}

int find_factorial(int n){
    int fact = 1;
    while (n>0)
    {
        fact *= n;
        n--;
    }
    return fact;
}

Using recursion function

#include<stdio.h>

int find_factorial(int n);

int main()
{
    printf("%d\n",find_factorial(5));
    return 0;
}

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

Explain how to use the recursion method to solve this problem.

Consider the following mathematical formula:

5! = 5*4*3*2*1
4! = 4*3*2*1

therefore,
5! = 5*4!

In that way,
n! = n*(n-1artwork)!

Artwork by Author

n number factorial is hence,

n! = n * (n-1)!

Consider the following image for a quick overview of what happens during the recursion process.

photo by Yashavant P. Kanetkar from Let Us C

As mentioned above, a recursive function can be used to solve this problem.

The only way to become an expert in recursion is to practice consistently. The URLs below will help you become an expert in recursion. Happy coding!

C programming exercises: Recursion - w3resource

Recursive Practice Problems with Solutions - GeeksforGeeks

The basic principle of recursive design is to make the parts have the same power as the whole.

— Bob Barton