Basics of Recursion

What is Recursion?

Recursion is the fundamental concept in programming that allows breaking down the problem into smaller subproblems. This can be useful in solving problems which can be defined in terms of similar subproblems like factorial of a number, Fibonacci of a number, towers of Hanoi, etc.

The formal definition of recursion is as follows:

Recursion occurs when a function calls itself either directly or indirectly. Each time a function is called with the smaller version of the problem until the condition is reached after which the function stops calling itself and returns. 

In a nutshell, it is an art of solving the problem by breaking it down into smaller subproblems and solving them.

The Components of Recursion

A recursive function has two components:

1. Base case
2. Recursive case

The base case is mandatory in a recursive function to stop recursion. Otherwise, it will run indefinitely. It is usually the smallest problem that can be solved without calling the function. For example, let’s say we are interested in calculating the factorial of some number n. Calculating the factorial of a number is a bit of work, but calculating factorial of 1 is easy (1! = 1). Calculating factorial of 1 is the smallest problem one can solve without calling the function. We can write the following piece of code in our function to calculate factorial of n as the base case:

if (n == 1) {  //If factorial of 1 needs to be found
    return 1;   // then return 1 as the result. 
}

On the other hand, the recursive case is where all the magic happens. It is the area of code in which the function calls itself every time with the smaller version of the problem. 

In the next tutorial, we will discuss a simple example of finding the factorial of n. There we will understand how a recursive procedure looks like in practice and how it is useful in solving the problem.