Understanding Recursion

Recursion is one of the most important concepts of programming paradigms. Most of your problems can be broken into smaller problems and solved through Recursion.

Definition

Recursion is the art/process of breaking a complex problem into
similar(to the original problem) smaller problems that can be solved with little or no effort.
In Recursion, a function calls itself directly or indirectly(wait for it).

Let's look at a simple recursive function.

const count = n => {
  if (n === 0) {
     return
  }
  console.log(n)
  count(n - 1)
}


count(10)

This function prints numbers from 10 to 1. Can you tell what's going on here?

1. The count function receives a parameter n(10).
2. It checks if n is equal to 0. If it is, then return and don't execute further.
3. Prints our parameter n(10).
4. Makes a recursive call to itself but changes n to 9.

The same process is repeated with n = 9, then 8, 7... so on until n finally becomes 0 and no more recursive calls are made.

Structure of Recursive Function

You might have guessed it by now, but let's go through the key elements of a recursive function anyway!

There are 3 main elements:

1. The base condition: Every recursive function should have a condition that stops its execution at some point. In our example, it's the first block where we check if n is equal to 0 or not. Without a base condition, we'd end up with a stack overflow error. Mostly, base conditions are a point where we cannot break our problem further or it's a special case for which the solution is already known.

2. Progress towards base condition: It's conspicuous that one has to tweak the parameter for the next recursive call else we'd end up calling the function with the same parameter and that'll get us nowhere. Our goal should be to reach the base case. In our example, n - 1 is passed every time for the recursive call.

3. Recursive call: Duh, How can it be recursion if a function doesn't call itself directly or indirectly?

Cool, got it! But what's this, direct and indirect call, I have been talking about?

Direct and Indirect Calls

When the recursive function call is made inside the function itself it's known as a Direct call. Like the example we just discussed.

function foo(n) {
  // some logic here
  foo(k)
}

When a function calls another function and the called function again calls the calling function, it's known as an Indirect call.

function foo(n) {
  // some logic here
  baz(k)
}

function baz(k) {
  // some logic here
  foo(n)
}

Thinking Recursively

Let's solve two common problems with the help of recursion and understand the process of thinking recursively.

1. nth Fibonacci Number

Fibonacci numbers, the elements of the sequence of numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, …, each of which, after the second, is the sum of the two previous numbers.

Even if you know the solution let's assume for a minute that this is a very complex problem. Now, your first objective is to break it into smaller problems.

Hmmm, think!

If I give you two consecutive numbers from the sequence, can you tell me the next number? 5 and 8? 13, right?

So, it's okay to say that for finding nth Fibonacci number you should know n - 1 and n - 2. Correct? Once you have those you simply add them to get the result.

Our function is starting to get some shape. Let's write down what we have until now.

function nthFibonacciNumber(n) {

  return nthFibonacciNumber(n - 1) + nthFibonacciNumber(n - 2)
}

Okay, so far so good! We have our recursive calls and little tweaking going on there. We are only missing a base condition.

So, in Fibonacci numbers, the first two elements are always known i.e. 0 and 1. We can craft our base condition based on these.

function nthFibonacciNumber(n) {
  if (n <= 1) {
    return n
  }
  return nthFibonacciNumber(n - 1) + nthFibonacciNumber(n - 2)
}

That's it! You've written your first recursive function. 🎉
Also, note that this is not the most efficient solution. This can be further optimized using Dynamic Programming based solutions. But hey, that's a start. 💪

2. Palindrome String

We have a string and we have to tell if it's a palindrome or not. A palindrome is a word or other sequence of characters which reads the same backward as forward, such as madam, racecar.

Let's consider madam as an example.

Hmmm, think!

If I tell you ada is a palindrome what additional work you have to do to find of madam is a palindrome? Compare m and m, right? First and last character? Correct!

That's it! You've broken your problem into a smaller problem.
Let's write a function for what we have so far.

function isPalindrome(text) {
  const l = text.length

  const res = isPalindrome(text.substr(1, l - 2))
  return text[0] === text[l - 1] && res
}

So, here I am calling the same function again but with a substring excluding the first and the last character. Finally, I do && of the res and compare the first and last character myself.

Calls made:
- `madam`
- `ada`
- `a`

We're only missing a base condition. Unlike the last example, we don't have a special case here. But we do know a point after which we cannot break our problem further i.e. when l reaches 0 or 1. At that point, we reach the mid of the string. Let's code that.

function isPalindrome(text) {
  const l = text.length
  if (l <= 1) {
    return true
  }
  const res = isPalindrome(text.substr(1, l - 2))
  return text[0] === text[l - 1] && res
}

Great work! You just wrote your second recursive function. 🎉

Tail Recursion (Bonus)

You've made it this far. Here's a bonus topic for you. 😉

You can optimize your recursive function by using tail recursion.
Let's see what is it!

function foo(n) {
  // logic 1
  foo(k)
  // logic 2
}


function baz(n) {
  // all the logic
  baz(k)
}

We have two functions foo and baz, both recursive in nature. But one is faster than the other even though both have the same purpose? Which one?

So, baz is faster than foo because it uses tail recursion. A recursive function is said to be Tail Recursive if it calls itself at the end of the function. Why is it faster?

When we use recursion, all the function calls all stored in the call stack, and until we reach the base case it keeps on adding more calls. After reaching the base case, the result is returned to its calling function which returns the result to its calling function, and so on until we reach the function from where this recursion originated.

With tail recursion, modern compilers have this capability to not store unnecessary calls in the call stack.

foo() has some more work to do after the recursive call so it stays in the stack and waits for its recursive call to finish and then executes the rest of the logic. Whereas, baz() doesn't have anything to do after the call recursive call so it gets removed from the call stack immediately. This results in faster execution as the last recursive call gives us the result.

Whenever possible, try to write a solution using tail recursion.

That's all folks! 👋

I hope you liked this read. 🙏 I'll be writing more on Algorithms and Data Structures.

🌏 https://thesanjeevsharma.now.sh