What is recursion?

If you have ever done a Computer Science Fundamentals course, you must have inevitably encountered this term. Don't fret if you have never come across this term or if it seems daunting, in this blog we shall discuss the basics of recursion and see how it can ease our troubles in programming.

Most of the content that covers recursion summarize this concept in 3-4 words, mainly

When a function calls itself, it is said to be recursive.

But why would a function call itself in the first place? Isn't it a function's job to solve the problem, and moreover if it calls itself, then this second function call will again call itself and will we enter an infinite loop? Not really, a correct and terminating recursive function has two major components :

1. A Base Case
2. A Recursive Call

The base case, is what makes sure that your function doesn't enter an infinite loop and actually terminates, and the recursive call is the function invoking itself with a slightly different input. (Why?)

The underlying concept / intuition for recursion is that the user doesn't explicitly solve the bigger problem, he only solves the easiest part, and lets recursion take care of solving the bigger problem. The caveat here is that the bigger problem must be solvable using solution of a smaller sub problem. That is to say if the smaller sub problem is solved, its solution can be used to solve the bigger problem.

I know this might seem difficult or too hard to grasp, but stay with me here, because once you get the hang of recursion it will become one of the most intuitive concepts in your programming journey.

Let us have a look at both of these (base case and recursive call) in detail, with the help of an example:

Write function that returns the sum of first n natural numbers.

Now this problem can easily be solved using a for loop or a while loop, but our goal here is not to solve the problem but rather understand how recursion works and how can it be beneficial.

To begin with, here we will not actually solve the complete problem in one go, but rather just solve the easiest sub problem and see if it can be used to solve the complete problem.

The first question we ask here is if we somehow knew the sum of first (n-1) natural numbers (Don't worry about how do we know? Frankly, we don't. But if we did) can we use it get the sum of first n natural numbers, and if yes , how? . How do we connect the solution of problem with n-1 natural numbers(Smaller sub problem) to get the solution to the problem with n natural numbers(Bigger Problem).

If we think carefully about just this issue, then it is not that difficult. If we some how had f(n-1) (let f(n) be the sum of n natural numbers), then f(n) will simply be f(n-1) + n. Does this make sense? Suppose I tell you to give me some of first 11 natural numbers(BIGGER PROBLEM) and tell you that the the sum of first 10(SMALLER SUB PROBLEM) is 55, you could easily say, 55 + 11 = 66. Yes this uses the concept of Mathematical Induction that you studied in your high school.

Now since we know how a sub problem's solution can be used to get the solution of a bigger problem, let us move on to the next step, the base case. What is the easiest sub problem (of the above bigger problem) that you know the answer to and can easily hard code it? We know that sum of first 1 natural number(s) is 1. So this becomes our base case, the terminating condition at which the function stops calling itself to solve smaller sub problems, because it knows the answer to the smallest sub problem and doesn't need to compute anything. This is the condition where recursion ends.

Although recursion is a language agnostic concept, we shall write the code in python for the sake of examples, as is it is one of the most human friendly languages, and very much like pseudo-code.

def sum_of_natural_nums(n):
    #Base Case
    if n==1:
        #we know the answer to the smallest sub problem, and if user enters n=1,
        #we return the answer right away, without performing other computations.
        return 1
    #The recursive call, to a smaller sub problem, instructing function to
    # get the solution for (n-1) numbers first, and then we add n to get 
    # the solution for n numbers.
    return sum_of_natural_nums(n-1) + n

It is important to note that in the last part of recursive call, we invoke the same function but a slightly different input that approaches the base case (n=1).

Common Pitfalls during recursion:

1. No base case, wherein the function is not called but instead some O(1) operation or value is returned.
2. Forgetting to return or returning the wrong thing in the base case. If no value is returned at the base case, then code doesn't end at the end of base case and reads the code after it eventually returning another function call.
3. Stack Overflow : When recursion doesn't stop due to any of the above reasons, the call stack (we'll discuss in a later blog post, for now assume a tracker that stores answers of previous call while waiting for next calls to finish) starts filling with infinite function calls, and since memory size is limited, the stack overflows giving error.

Recursion is an exhaustive concept mastered through a lot of practice, but I still hope this post was able to throw some light on what recursion is and how it works at the root level. Almost all of recursion works on the basic principles of correct base case, recursive call with a different input (such that it moves towards the base case), and can help solve a lot of interesting problems which otherwise seem very difficult. Recursion eases a lot of Binary Tree problems because of the binary tree data structure is stored and imagined. All in all this is a concept that should be understood well and utilised.