Intro to Recursion: A Beginner's Guide

Learning about Data Structures, i struggled to understand recursion. It was a thorn in my side, kinda. It sounds intimidating, when you're new to it. In this tutorial, i'll introduce you to its key principles, and provide examples to help you understand and implement recursive functions.

What really is Recursion?

Recursion is just when you have a function that calls itself directly or indirectly. It breaking down a larger problem into smaller, more manageable sub-problems that follow the same pattern as the original problem.

How a recursive function looks like

A recursive function 'typically' consists of two parts:

A Base Case: This is the stopping condition that prevents infinite recursion. It defines when your function should stop,(unless you want it to run till the new year :)).

A Recursive Case: It defines the problem using a smaller sub-problem that can be solved using the same function. The function calls itself with modified inputs to progress towards the base case.

There you have it, let's look at what this looks like using one of he most known recursion functions.

Let's visualise this

Think about calculating the factorial of a number. You start with the base case when the input is 0 or 1, and the factorial is defined as 1. For any other input, we break it down into a smaller sub-problem until we reach the base case.

Have a look in the factorial function below:

function factorial(n):
   if n equals 0 or 1:
       return 1
   else:
       return n * factorial(n - 1)

The function above calculates the factorial of a given number n.

Our function 'factorial' uses the if statement to handle the two cases:

the base case:

If n equals 0 or 1, which are the smallest factorial values, the function returns 1.
This acts as the stopping condition for the recursion since there are no more smaller sub-problems to solve.

the recursive case:

If n is greater than 1, the function enters the recursive case.
It calculates the factorial of n by multiplying n with the factorial of n - 1.
This recursive call reduces the problem size and progresses towards the base case.
The result of the multiplication is returned as the final factorial value.

Is this still giving you a headache?

Here's an example to illustrate the execution of the factorial function for n = 4:

1. The initial call is factorial(4).
2. Since n is not 0 or 1, the function enters the recursive case.
3. It computes 4 * factorial(3).
4. The next recursive call is factorial(3), which further reduces the problem.
5. This process continues until the base case is reached:
   • factorial(2) = 2 * factorial(1).
   • factorial(1) returns 1, and the recursion starts unwinding.
   • factorial(2) returns 2 * 1 = 2.
   • factorial(3) returns 3 * 2 = 6.
   • Finally, factorial(4) returns 4 * 6 = 24, which is the factorial of 4.

Recursion is just one approach to problem-solving, and it's important to understand its trade-offs compared to looping. With a solid understanding of the principles and examples, you can begin incorporating recursion into your programming arsenal.

This is my first article guys, and i hope that was helpful so i'lld like to know your opinion. Happy coding!