The first time I heard of recursion was in the popular Harvard CS50x course hosted on EdX- Introduction to Computer Science and Programming. The course instructor, Professor David Malan, introduced the concept while teaching algorithms (using C). Even though I wasn't a newbie programmer, I found the concept quite confusing, yet fascinating as well. I decided to dig deeper and in my bid to understand the idea, I came up with a simple illustration.

Imagine you are taking part in a treasure-hunt game that required you to open doors in search of a treasure. You find that every successive door you get to open is smaller than the previous- until you find the treasure behind the smallest door possible. That is recursion. You are performing the same task each time (opening a door) but on a smaller version until you reach a condition i.e. when you open the smallest door.

This is what a recursive function does. It keeps calling itself (i.e. repeats) until a certain condition(s) is/are met.

Recursion is a programming technique whereby a function calls itself as part of its execution. The technique itself derives its name from the English word 'recur' which means to repeat. In other words, a recursive function repeats itself within the block of code that defines the function, but each successive function call acts on a smaller strand of the original problem.

A typical real-world example of a recursive function is the factorial function in math defined as follows:

                 n! = n x (n-1) x (n-2) x (n-3) x...x 1

For our purposes, we will simply write the factorial of a positive integer n as fact(n) such that

fact(6) = 6x5x4x3x2x1

fact(5) = 5x4x3x2x1

fact(4) = 4x3x2x1

fact(3) = 3x2x1

fact(2) = 2x1

fact(1) = 1

In general, the factorial of any given positive integer n is the product of all positive integers beginning from n down to 1. Moreover, you should notice a pattern here as highlighted below:

fact(6) = 6 x fact(5)

fact(5) = 5 x fact(4)

fact(4) = 4 x fact(3)

fact(3) = 3 x fact(2)

fact(2) = 2 x fact(1)

fact(1) = 1

Going by this observation, we can now say that fact(n) = n x fact(n-1) i.e. the factorial of a number is the product of the number and the factorial of the number immediately below it.

Without using recursion, the factorial of n may be computed using loops as follows:

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

However, the downside of using loops is that they usually have greater runtimes and one could easily run into errors. Conversely, the use of the recursion technique provides faster runtime and also presents a more elegant solution to the same problem as seen in the code snippet below:

int fact (int n)
{
  //base case
  if (n == 1)
  {
    return 1;
  }
  //recursive case
  {
  else
  {
    return n * fact (n-1);
  }
}

As highlighted by the comments in the code above, every recursive function consists of two conditional cases that determine whether the recursion will proceed at any given instance or not. This is important because a recursive process cannot proceed indefinitely and hence has to be truncated at some point.

The base case terminates the recursive process when triggered. Here, it occurs for the value of fact(1), which simply returns 1.

The recursive case, if satisfied, signals the recursion to proceed.

Per the earlier illustration, the smallest(final) door opened will be the base case since the process terminates thereafter and the search is stopped. Every other door opening is part of the recursive case.

It is also possible to have more than one base case or recursive case, as the program might recurse or terminate in different ways, depending on the input being passed in. A typical example is a recursive solution to the Fibonacci series. (You can see that here).

The technique of recursion finds wide application in several algorithms used in the world of computer science and programming. The "binary search" algorithm, for instance, also known as the divide and conquer strategy, employs the modus of recursion to iteratively search for a specific value among a set of values.

Lastly, it is important to note that recursive functions might actually be used to replace loops in non-recursive functions but this is not always the case.