Recursion in JavaScript

Recursion in JavaScript

What is Recursion?

Why do we need to know Recursion?

How recursive functions work?

Examples:

Without recursion:function countDown(num){
for(var i = num; i > 0; i--) {
console.log(i);
}
console.log("All done!");
}
countDown(5);With recursion:function countDown(num){
if (num <= 0) {
console.log("All done!");
return;
}
console.log(num);
num--;
countDown(num);
}
countDown(3);//print 3
//countDown(2)
//print 2
//countDown(1)
//print 1
//countDown(0) - base case
//print "All done"
function sumRange(num){
if (num === 1) return 1;
return num + sumRange(num-1);
}
sumRange(3);
//return 3 + sumRange(2)
// return 2 + sumRange(1)
// return 1 - base case
// 3 + 2 + 1 = 6
Without recursion:function factorial(num){
let total = 1;
for(var i = num; i > 0; i--) {
total *= i;
}
return total;
}
factorial(5); //120With recursion:function factorial(num){
if(num === 1) return 1;
return num * factorial(num-1);
}
factorial(3); //6

Common Recursion Pitfalls

Helper Method Recursion:

function outer(input){
var outerScopedVariable = [];
function helper(helperInput){
//modify the outerScopedVariable
helper(helperInput--)
}
helper(input)
return outerScopedVariable;
}
//Two functions - outer(main) and helper (recursive)
//Commonly done when we need to compile an array or list of data.
function collectOddValues(arr){
let result = [];

function helper(helperInput){
if(helperInput.length === 0){
return;
}
if(helperInput[0] % 2 !== 0){
result.push(helperInput[0]);
}
helper(helperInput.slice(1))
}
helper(arr)
return result;
}
collectOddValues([1,2,2,4,4,5,6,7,8]) //(3) [1, 5, 7]

Pure Recursion:

function collectOddValues(arr){
let newArr = [];

if(arr.length === 0){
return newArr;
}
if(arr[0] % 2 !== 0){
newArr.push(arr[0]);
}
newArr = newArr.concat(collectOddValues(arr.slice(1)));
return newArr;
}
collectOddValues([1,2,3,4,5]) //(3) [1, 3, 5]
//[1].concat(collectOddValues([2,3,4,5]));
// [].concat(collectOddValues([3,4,5]));
// [3].concat(collectOddValues([4,5]));
// [].concat(collectOddValues([5]));
// [5].concat(collectOddValues([]));
// []
//[1,3,5]

Recursion examples:

function power(base, exponent){
if(exponent === 0) return 1;
return base * power(base,exponent-1)
}
power(2,0) // 1
power(2,2) // 4
power(2,4) // 16
function productOfArray(arr){
if(arr.length === 0) return 1;
return arr[0] * productOfArray(arr.slice(1))
}

productOfArray([1,2,3]) // 6
productOfArray([1,2,3,10]) // 60
function fib(n){
if (n <= 2) return 1;
return fib(n-1) + fib(n-2);
}
fib(4) //3
fib(6) //8
fib(10) //55
//n = 4
//fib(3) + fib(2)
//[fib(2)+ fib(1)] + 1
//1 + 1 + 1
//3
//n = 6
//fib(5) + fib(4)
//[fib(4)+ fib(3)] + [fib(3)+ fib(2)]
//[fib(3)+ fib(2) + fib(2)+ fib(1)] + [fib(2)+ fib(1) + 1]
//[fib(2) + fib(1)+ fib(2) + fib(2)+ fib(1)] + [fib(2)+ fib(1) + 1]
//[1 + 1 + 1 + 1 + 1] + [1 + 1 + 1]
//8
function reverse(str){
if(str.length === 1) return str[0];
return str[str.length - 1] + reverse(str.slice(0, str.length-1))
}
// reverse('awesome') // 'emosewa'
// reverse('rithmschool') // 'loohcsmhtir'
Helper method:function flatten(arr){
let resultArr = [];
function inner(arr){
for(let i = 0; i< arr.length; i++){
if(Array.isArray(arr[i])){
inner(arr[i]);
}
else{
resultArr.push(arr[i])
}
}
}
inner(arr);
return resultArr;
}
flatten([1, 2, [3, 4, [5, [6, 7, [[[8]]]]]]]) //[1, 2, 3, 4, 5, 6, 7, 8]Pure recursion:function flatten(arr){
let resultArr = [];
for(let i = 0; i < arr.length; i++){
if(Array.isArray(arr[i])){
resultArr = resultArr.concat(flatten(arr[i]))
}
else{
resultArr.push(arr[i])
}
}
return resultArr;
}
// flatten([1, 2, 3, [4, 5] ]) // [1, 2, 3, 4, 5]
// flatten([1, [2, [3, 4], [[5]]]]) // [1, 2, 3, 4, 5]
// flatten([[1],[2],[3]]) // [1,2,3]
// flatten([[[[1], [[[2]]], [[[[[[[3]]]]]]]]]]) // [1,2,3]

Web developer who loves to code and help others code :)

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store