Algo Basics 101: Recursion Review

Recursion is when you define something in terms of itself, or simply it is a function that refers to itself inside of the function. It is a function that calls on itself inside itself.

Recursion is really good for tasks that have repeated subtasks to do. Like when we want to look through every folder and its subfolders or traversing nested objects.

This concept is used heavily in sorting algorithms and searching algorithms, such as when we traverse a tree.

Stack Overflow
When a call stack is overflowing with function calls, then that is a stack overflow. Think of it like if each function is like some amount of water and if you keep adding that amount of water to a cup, then the water overflows from the cup.

In this case we run out of memory if we keep putting too many stacks in the call stack.

Recursion’s big issue is having an infinite call loop allowing it to go on forever if there is no way to stop this recursive call.

Interview Question: What is a problem with recursion?

Answer: The computer needs to allocate memory to remember things so a stack overflow can occur when we have recursion and there is no way to stop the recursive call (if you have no base case). Basically the computer runs out of memory to store all of your function calls in its call stack.

Anatomy of Recursion
Every recursive function needs a base case or a stopping point where the function is no longer calling on itself.

It’s like the point where you finally unravel the entire ball of yarn you’ve spun by repeatedly calling the function (spinning the yarn into a ball I guess). Think of the base case like the string you pull to finally unravel a huge complicated knot.

In the case of getting all the items in a folder and its subfolders, our base case would be telling the program to stop when there are no longer any more folders in the subfolder.

Recursive functions have two paths:

recursive case: this is the case where we call the function itself again and run it
base case: this is the case where we say stop calling the function
In this example, there will be an undefined return:

let counter = 0;
function inception(){
    if(counter > 3){
       return 'done!';
    }
    counter++;
    inception();
}

But why does it return undefined? This is because this is essentially what we’re doing:

inception(inception(inception(inception(inception()))))

So now it goes like this:

inception(inception(inception(inception(‘done!’))))

Now on the inside we have inception(‘done!’) which doesn’t actually return anything. When a function doesn’t return anything, it just returns undefined. So we have to tell the function the return ‘done!’ and bubble it up.

You want to make sure that you always return so the value you want gets bubbled all the way to the top.

In this case, the correct way to write this recursive function so that it returns ‘done!’.

let counter = 0;
function inception(){
    if(counter > 3){
      return 'done!';
    }
    counter++;
    return inception(); // we have to add this return statement to bubble up 'done!'
}

If you don’t do this, the result will never be bubbled up.

Here are the steps for writing a recursive function:

Identify the base case.
Identify the recursive case.
Get closer and closer and return when needed or when you reach your desired base case. Usually you have two returns, one for the base case and one for the recursive case, the latter of which to bubble up the return from the base case.
Conclusion
Identifying the base case will allow you to write recursive functions a lot easier. I wanted to write this quick review and guide so that people can always refresh on the basics.

Never forget to review your basics.

Happy coding and happy new year!