Data Structures and Algorithm Concepts: Recursion
What is a recursive function and why are they extremely important in understanding algorithms? I’m going to explain recursion in the best and simplest way I can.
In the simplest terms possible, a recursive function is a function that calls upon a smaller version of itself in order to get to the solution. There is a pattern where by repeating the function over and over again, we can arrive at the solution. One of the key points of recursion is that it must have a base case, or a case when the recursion must stop. This is known as the end condition.
The reason I have matryoshka dolls as the photo above is because it is a very good visual representation of what recursion is like. Every single doll has a smaller version of itself inside until we reach the absolute smallest one — in which it no longer has any more smaller ones within it. In a recursive function, the smallest one would be the base case.
Let’s go over a simple problem that could utilize recursion. In a previous blog post, I went over reversing a string. Well, did you know that there’s a recursive solution to that which only requires 3 lines of code?
Let’s walk through this one step at a time because it might seem a little confusing at first. I’ll explain how the built-in JavaScript functions substring and charAt work, and then I’ll explain the base case (the if condition).
According to MDN Documentation, the substring method returns the part of the string between the start and end indexes, or to the end of the string.
In this example, with a given string of “abcdefg”, calling the substring method on it with the start index of 0 and end index of 3 will return “abc”. Be careful not to confuse this method with substr, which takes the arguments of a starting index and the number of characters to include instead. Both can be used in this function, but I’ll be sticking with the substring method.
The next method to discuss is charAt. According to MDN, the charAt method returns a new string consisting of the single UTF-16 code unit located at the specified offset into the string. In simple terms, this means that given the argument of an index, charAt will return the character at that given index.
In the above example, charAt(5), when called upon the string of “abcdefg”, returns the character at the 5th index, which is “f”. (Remember that the first character’s index is 0!)
Now let’s go back over to the base case scenario:
In the base case, whenever the string is empty, we will simply return an empty string and stop the recursing. This is the smallest part of the string we can have. This will make more sense once we start iterating through the recursive function.
Let me place the full function here for easier reference:
Let’s say we run the reverseString function on the string “hello”. The first time we run it, the function will check if the string is empty and since it isn’t, it will run the next line, which calls the function again with a new argument of substring(1). Calling substring(1) on “hello” with just one argument returns the characters from the given index to the end of the string, in this case, returning “ello”. We then add on charAt(0), which is the first character of the string to the back of the string BUT it does not return up the chain yet,because the function get called again on “ello”, this time returning the substring “llo” with “e”. This continues down the string until we hit the empty string base case. Here’s a more visual diagram of the entire return chain:
Every time the function is called again, a letter from the start is taken off and added to the end, but not until we have hit the base case and are on our way back up the return chain does the letter being added on actually get added.
Hopefully that made some sense! GeeksforGeeks has a slightly more complicated explanation, but feel free to check it out as it might help your understanding of recursion even more.
Recursion may be a handful, but as you practice more problems involving recursion, it will begin to make more and more sense. The other important aspect to consider when implementing recursion in a solution is to look at the time and space complexity. Recursion can oftentimes not be the most efficient solution, so it is important to keep in mind that any recursive solution always has an iterative solution as well. With the reversing string solution, my previous blog covers the iterative solution. Due to the recursive nature of the solution, you can imagine that the time and space complexity of a recursive solution will quickly increase significantly as the number of function calls start to increase. Imagine trying to reverse a string with 25 characters. We’d have to make 25 different function calls, one within the other!
Knowing recursion is just another way to demonstrate your knowledge of solving algorithms to your technical interviewer. This is just another piece of the puzzle to improving your technical interview performance. Although recursion can seem extremely confusing at first, as with any topic, the more you practice, the easier it is to wrap your head around it.
Next week, I’m going to dive into a recursive solution for solving the Fibonacci sequence! Here’s a sneak peak into what the N-th Fibonacci Sequence question looks like:
Given an integer (n), print out the n-th number entry within the Fibonacci sequence. For example, fibonacci(6) will return 8.
Have fun and as usual, don’t forget to take breaks when coding!
Enjoyed this article? If so, get more similar content by subscribing to Decoded, our YouTube channel!
