Breaking the Recursive Code.

Abhishek Singh
6 min readJun 26, 2020

--

Photo by Cristina Gottardi on Unsplash

“In order to understand recursion, one must first understand recursion.”

You must have heard Recursion is basically a function calling itself, and your brain goes like WHAAAT??

You see a reflection of the reflection of the reflection of the refl… or a dream within a dream within a dream…. Ooohh INCEPTION

Before moving to recursion let’s try to revise the Principle of Mathematical Induction (PMI). It has a 3 step process.

  • Base Case: In this concept firstly we do for (n = 0 or n= 1 usually) for making the LHS and RHS true.
  • Induction Hypothesis: We have to assume that it is true of P(k).
  • Induction Step: Then we will prove that this relation holds true for the condition (n = K+1) using step 2

Just some basic mathematics below

Sum of first n natural numbers is :

1 + 2 + 3 + — — — — — + n = n(n+1)/2

In step 1 we will prove f(n) for n =1

for n = 1, we have LHS = 1

and RHS = 1(1+1)/2 =1

LHS = RHS

In step 2 we will assume this relation holds true for n = k

P(k) is 1 + 2 + 3 + — — — — — + k = k(k+1)/2

In the last step, using the assumption step, we will prove that this relation holds true for n=k+1

P(k+1) is 1 + 2 + 3 + — — — — — + k + k+1= (k+1){(k+1) + 1}/2

Now from step 2, we can substitute the value

P(k+1) becomes k(k+1)/2 + k +1 = (k+1)(k+2)/2

(k+1)(k/2 + 1) = (k+1)(k+2)/2

(k+1)(k+2)/2 = (k+1)(k+2)/2

LHS = RHS

After this 3-step process, I can say that this relation is valid for all natural numbers.

So what is Recursion and how is this related to Recursion?

Recursion is the process of breaking down a bigger problem into smaller sub-problems (of the same kind) until you reach a trivial/base case, which is solved immediately. As opposed to iteration, which attempts to build up to a solution, recursion aims to break a problem down to its most basic form.

Parts of Recursive Algorithm

A Recursive case, in which the function must call itself to break the current problem down to a simpler level.

A base case, in which the function can return the result immediately. Without this, the program would have no end condition and therefore would loop infinitely.

Let’s create a function that counts down from a given number.

1. Iterative/Imperative approach

In this Algorithm :

  1. Takes one parameter called number.
  2. Prints everything from number to 0.

2. Recursive Approach

Each recursive solution is built on following these 2 steps:

Try and break down the problem into subproblems.
  1. Try and break down the problem into subproblems. Defining expectation and faith.

Here the expectation is the problem we need to solve. Faith is our assumption i.e; we just have to solve for one case, and the rest subproblem will be solved by Recursion.

Keep calm and trust recursion! Assume that your recursive calls to the subproblems will return the information you need.

2. Finding the base case can be obtained in two ways. Either we Input the smallest subproblem or the Last Call Stack (Recursion will move to the end).

Let’s have a look at the above program with a recursive approach

This Algorithm also :

  1. Takes one parameter called number.
  2. Prints everything from number to 0.
Call Stack

The main difference between the two approaches.

  1. Iterative uses internal state (extra variables for counting, etc).
  2. Recursive does not need an extra variable to track its progress, it simply passes updated parameters between each call.

Recursion follows a well-known algorithm design technique called divide and conquer which means breaking a problem into subproblems of the same or related type until the subproblem becomes simple enough to be solved directly. The solutions to the subproblems are then combined to give a solution to the original problem.

Let’s solve another simple Problem (I promise this is the last one)

Let us see how we can find out the factorial of a number. Before that, let’s see what the factorial of a number represents and how it is calculated.

factorial(N) = 1 * 2 * 3 * . . . . . . . . . N-1 * N

Simply put, the factorial of a number is just the product of terms from 1 to the number N multiplied by one another.

Extra Variables for a simpler explanation

Let’s take a look at the Call Stack:

Pros of Recursion

For all those people who want to make their code look pretty as a picture, recursion is the best way to do that. Recursion makes code more compact, readable and so very elegant.

Some functional languages implement tail call optimization wizardry. So basically, what happens is, if a function’s return expression is a result of a function call, the stack frame is reused instead of pushing a new stack frame in the call stack.

Cons of Recursion

Recursion uses more memory because the function has to add each call and keep its value there until the last call will be done. In this way, it takes more memory than the iterative approach.

Recursion can lead to the perils of stack overflow. When most programs start, they allocate a single chunk of memory to the stack, if that memory is used, the entire program crashes due to stack overflow.

A template for TopDown and BottomUp Recursion

To effectively use recursion, it takes practice to master. Here is a comprehensive overview with further examples from popular recursive algorithms.

Also Some Popular Interview Questions :

  1. Tower of Hanoi
  2. LinkedList reversal
  3. Merge Sort
  4. Quick Sort
  5. Pairwise Swapping in LinkedList
  6. Tree Traversals
  7. Binary Search

I hope my first article made sense to you & helped you learn something new about Recursion today. If not, well you tried. AND THAT’s THE FIRST STEP TO GROW, my friend. I’m no pro, just another programmer reaching out to other programmer buddies. Keeping it crisp, feel free to ping me with any doubts, criticise me for negligence and appreciate if worthy.

Stay tuned for the next blog where we will cover Backtracking and use recursion in order to explore all the possibilities until you get the best result for the problem.

If you’ve managed to read the article this far (not necessarily in one stretch), you’re awesome.

--

--