Recursion - rohit120582sharma/Documentation GitHub Wiki
A process (a function in our case) that calls itself.
Recursive functions should always have a base case and be invoked with different input each time. The idea is basically taking one problem and doing it over and over on a smaller piece or on a changing piece until you hit some endpoint which we call the base case.
Two essential parts of a recursive function!
- Base Case : The condition when the recursion ends.
- Different Input
Time/Space complexity
- Measuring time complexity is relatively simple. You can measure the time complexity of a recursive function as then number of recursive calls you need to make relative to the input.
- Measuring space complexity is a bit more challenging. You can measure the space complexity of a recursive function as the maximum number of functions on the call stack at a given time, since the call stack requires memory.
ES2015 allows for tail call optimization, where you can make some function calls without growing the call stack.
By using the return keyword in a specific fashion we can extract output from a function without keeping it on the call stack.
Unfortunately this has not been implemented across multiple browsers so it is not reasonable to implement in production code.
- JSON.parse / JSON.stringify
- document.getElementById and DOM traversal algorithms
- Object traversal
- Search for something across data structures like trees or graphs often involve recursion as a solution.
- Very common with more complex algorithms
- It's sometimes a cleaner alternative to iteration
Helper method recursion is an alternative that allows us to use an external scope in our recursive functions.
function collectOddValues(arr){
// Create object
let result = [];
// Create helper function
function helper(helperInput){
if(helperInput.length === 0) {
return;
}
if(helperInput[0] % 2 !== 0){
result.push(helperInput[0])
}
// Call itselt with changed input
helper(helperInput.slice(1))
}
helper(arr);
// Return result
return result;
}
collectOddValues([1,2,3,4,5,6,7,8,9])
Pure recursion eliminates the need for helper method recursion, but can be trickier to understand at first.
function collectOddValues(arr){
// Create object
let newArr = [];
if(arr.length === 0){
return newArr;
}
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
// Call itselt with changed input
newArr = newArr.concat(collectOddValues(arr.slice(1)));
// Return result
return newArr;
}
collectOddValues([1,2,3,4,5])