Data Structure Recursion
Recursion is one of the difficult techniques to solve Data structure problems. It looks like a loop concept but it’s not easy to understand like how loops work. You can solve some problems with the loops but recursion does not require local variables to maintain local state. Recursion is also easy to write the code and test because they are pure manners. They are returning specific consistent value given input.
Recursion can be used in many situations. But most effective used in solving problems. You can use recursion iterative branching like fractal math, sorting or traversing nodes of complex or non-linear data structure.
Decomposing Recursion
- A recursive function class itself.
- A recursive function has two main parts.
- A terminating condition (base case) is the stop to calling function to avoid infinite loop over and over again.
- Recursive case (this is the part of function call itself).
Recursion function
Let’s dive in and see how recursion works in the function and try to understand each step while we are computing the numbers and get the final number.
function factorial(num) {
if (num === 1) return 1; //(base)return num * factorial(num - 1); //(Recursive Call)}console.log(factorial(5))// output: 120
Breaking code down
As you see above we have a recursive function that calls itself. We passed a number with this function. Whatever number is passed in will return the factorial of that number.
First we have to break points for this function. First of all we want to multiply the number by the number that is one less than the computed number.
Recursive call
return num * factorial(num - 1); We are basically implementing a subset and we can repeat that subset which makes it ideal for Recursion. As we see we are returning num times * factorial(num — 1) and when we call the function we will go and multiply with smaller number. Then it will return number (x) but it will call function again till the terminating condition(base). It’s mean where we implemented a condition to stop repeating this process.
Base(Terminating condition)
if (num === 1) return 1; //(base)As you understand the condition when the number is equal to the one it has to return one;. It will end our recursive call and stop repeating the function call itself.
Illustrating Recursion
5*factorial(4)
5*4*factorial(3)
5*4*3*factorial(2)
5*4*3*2*factorial(1)
5*4*3*2*1
5*4*3*2
5*4*6
5*24
result =120
Debugging Recursion & Stacks
I want you to pay attention to the stack part during the debugging process. As you see variable num: 5 each time we call the function the value of the number would change. You can see the value of the number on the scope on the left side.
You can also see once we call the function it’s stored on stacks to compute the final result on the end. Initially the function calls anonymously on the call stack. Function is assigned to variable factorial(5) was invoked. From there it began to call itself and use the name we assign to function factorial. Each time we execute to code and call the recursive function it will be added on stack. If you take a closer look at the call stack part, you can also understand how to stack working with recursion. Debugging gives us the ability to understand each step of recursive function execution to make it clear. If you are a new beginner I highly recommend you to debug your code when you work on recursion. Debugging Recursive functions also makes a better understanding of how stacks are working with recursion and why we need those data structures.
When it will arrive at the number (1), it will return as we put the terminating condition as the base point and the function will stop calling itself. Since we are at the bottom of the function we returned the final number(120) on the end.
Where Do We Use Recursion
- JSON.parse / JSON.stringfy
- Document.getElementById and DOM traversal algorithms
- Object Traversal
- Complex data structures
Where things can go wrong when you implement a recursive function
- No Base Case or wrong base Case
- If you forget put base case your code just keep going and going and adding to function calls to the stack over and over
- Forgetting to return or returning the wrong thing
- Stack Overflow!
Memoization
You don’t have to play around with recursion for long to realize that it’s pretty easy to overwhelm your computer. This is because most recursive functions are O(n²) or even O(n!). Since JavaScript runs on call stacks every time a new recursive layer is added, a lot of memory and processing power must be used to manage it all, despite most of it being redundant.
Time Complexity
In case of iterations, we take a number of iterations to count the time complexity. Likewise, in case of recursion, assuming everything is constant, we try to figure out the number of times a recursive call is being made. A call made to a function is Ο(1), hence the (n) number of times a recursive call is made makes the recursive function Ο(n).
Space Complexity
Space complexity is counted as what amount of extra space is required for a module to execute. In case of iterations, the compiler hardly requires any extra space. The compiler keeps updating the values of variables used in the iterations. But in case of recursion, the system needs to store activation records each time a recursive call is made. Hence, it is considered that space complexity of recursive function may go higher than that of a function with iteration.
Problems (in life and also in computer science) can often seem big and scary. But if we keep chipping away at them, more often than not we can break them down into smaller chunks trivial enough to solve
Recursion is a separate idea from a type of search like binary. Binary sorts can be performed using iteration or using recursion. There are many different implementations for each algorithm. A recursive implementation and an iterative implementation do the same exact job, but the way they do the job is different. Recursion involves a function that calls itself. Iteration uses a counter to track through a structure or complete an operation n times.
