Recursion

Introduction

Recursion is a programming technique in which a function calls itself. If the problem can be divided into smaller versions, the function can call itself with these smaller subproblems.

The concept of dividing a problem into smaller versions is not uncommon. We have encountered it several times in school math, for instance, when calculating the factorial.

Factorial of a number

Let’s take an example. A factorial of a number N, denoted by N!, is the product of all positive integers less than or equal to N. 4! would be 4 x 3 x 2 x 1.

Can we represent factorial in terms of a smaller version of itself? Yes! because 4! is simply 4 x 3!

Each recursive call tackles a simpler version of the original problem. This process continues until a base case is reached, which is a simple condition that can be solved directly without further recursion. What do you think is the base case of factorial? A factorial of 1 and 0 is 1.

Let’s look at the following code that calculates the factorial of the number 4.