Getting Started with Recursion in C

Introduction

Recursion is a programming concept where a function calls itself repeatedly (directly or indirectly) in order to solve a problem by breaking it down into smaller and simpler versions of the problem.

A recursive has the following characteristics:

• Base case: Prevents an infinite loop when the program is run by stopping the recursive function and terminating the program.

• Recursive call: Occurs when a function calls itself to solve a problem repeatedly.

Syntax

return_type recursive_func()
{
    /* Base call - stop the program */
    /* recursive_func() - recursive call*/
}

Steps to create a recursive function

1. Define a base case: Identify the simplest case in which the problem can be solved. Ensure it is able to terminate the program when it is reached.

2. Define a recursive case: Identify a way in which you can use your function to break down a problem into a simpler one.

3. Ensure the program terminates: Once your program reaches a base case make sure it is able to quit to avoid an infinite loop.

4. Combine the solutions: Put the solutions together to form a recursive function.

Example

We will solve a factorial problem to understand recursion. The first step is to understand our problem. To do that we will find out what is a factorial. A factorial is the product of positive integers less than or equal to the integer. It is denoted by this character !.

In this case, let's try to find a factorial of 4:

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

In the above example, you notice that the factorial of four is four times the factorial of three (4 * 3!). We can use recursion to solve this. The first step is to identify our base case. To do that let's break it down.

4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1 /* Base case */

We are now able to get our base case, which is the smallest possible solution to our problem. Once we do that, we go back to our problem and then break it down until we reach our base case. Next, let's apply this to a C program.

#include <stdio.h>

/**
 * factorial - Finds the factoial of a number.
 * @number: The number its factorial
 * 
 * Return: Factorial of a number
 */
 int factorial(int number)
 {
     /* Base case*/
     if (number == 0 || number == 1)
         return (1);

    /* recursive call */
    return (number * factorial(number - 1));
 }

/**
 * main- Entry point
 * 
 * Return: 0 (Success)
 */
 int main(void)
 {
     int fact = factorial(4);
     printf("Factorial: %d\n", fact);
     return (0);
 }

Output:

Factorial: 24

The first step in the above code is to check the base case, if it doesn't meet the condition it moves to the recursive call in doing so the problem is broken down until we reach our base case.

Exercise Get the user input and find factorial of the number provided using recursion.

Conclusion

If you’re struggling with recursion, I’d highly encourage you to experiment. See what works and what doesn’t. Remember that practice makes perfect.

Happy coding!