Recursion!... But Make It Simplified

Recursion — TheBurningMonk.com

What is Recursion?

In computer programming, Recursion, or a Recursive function, is a function that calls itself!

A simple analogy to what recursion is would be if you owned a Russian stacking doll. There is the first doll that is large in size, however, when you open it up, there awaits another doll, just slightly smaller in size! You realize that you can open up that doll to reveal another one just like it, only slightly smaller! This is a continuous activity until you have come to the very last doll, which then breaks the cycle. This is a visual representation of recursion!

Russian Stacking Doll Gif — Tenor

Wouldn’t A Recursive Code Lead To An Infinite Loop?

It is very possible! However, like a normal for loop or while loop, recursion has a break/exit condition so that the function does stop calling itself!

Here is a simple example of a count down function using recursion:

function countDown(n){
console.log(n)
if(n > 1){
countDown(n -1) // recursive call
} else {
return true // base case
}
}
countDown(5)
// 5
// 4
// 3
// 2
// 1
countDown(-1)
// - 1 
// true

The break down:

We have a function called countDown that takes in an argument of (n). What we want our code to do is replicate a count down sequence. Therefore, we create a conditional saying:

if (n) is greater than 1 then call countdown and with that same number we passed in the beginning, subtract it by one, and repeat the sequence of checking if n is greater than one.

By default, we must also create a base case to prevent us from entering an infinite loop, which is our return true statement. This will default to true with anything less than 1 is passed in.

Simply put our code is doing this:

countDown(5)
 countDown(4)
  countDown(3)
   countDown(2)
    countDown(1)
    return
   return
  return
 return
return

So What Are the Pros and Cons of Writing Recursive code?

Good question! Well to better answer that, let's look at the pros and cons of performing recursive code!

Pros:

• Recursive code can reduce the time complexity:

What I mean by this is in some cases, recursion, compared to iteration, reduces the time it takes for a function to complete. By taking up fewer lines of code, that makes room for our code to finish the function calls faster. Especially when we factor in memorization to help optimize and speed up our code.

In computing, memoization or memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again. — Wikipedia

Although I would like to add that, recursion will not always be the fastest option as opposed to iteration!

• Recursion is easier to debug

Some might agree that this is a greatly appreciated advantage to writing code. Recursion is simple to debug because of how little code you need to solve a problem.

Cons:

• Recursive code takes up space!

A Recursive function takes up a significant amount of memory space while being executed. Meaning that with every call being made, an element is being added to the stack and will stay there till either the function is completed by finding the answer or through the base case.

• Leads to reduced speed

I know I mentioned above that with memorization, our code can be a lot faster than if we implemented a function with a for or while loop. Well, that is not always the case when our recursive function is written poorly, we run the risk of our stack getting too full, eventually leading to reduced speed and program crashes.

What is this “Stack ” you mentioned?

Great Question!

A stack is a data structure that operates on a “Last In, First Out” basis. An item is “pushed” onto a stack to add to it, and an item is “popped” off the stack to remove it. — freecodecamp

What's great about stack data structures is that it is fast! Its Big O complexity is O(1). This is because stack does not need the use of loops, fortunately, there is the use of pop(), push(), and empty().

leggo stacking

So, Should I Use Recursion Instead Of Iteration?

Both methods are equally efficient for problem-solving, however, to answer your question, it depends on the problem that is presented to you!

Recursion is efficient to use when you are dealing with branches that are too complex for a loop to iterate through. Being mindful of the cost of space and reduction of time that follows with a recursive function that stacks on too many elements.

Iterations are just as effective in speed and optimization, it takes up less stacking space and the readability is easier to understand as it is more clear in what is happening in the loop.