# Recursion

So, what is recursion?

A recursive function is a function that calls itself until a “base condition” is true, and execution stops.

While false, we will keep placing execution contexts on top of the stack. This may happen until we have a “stack overflow”. A stack overflow is when we run out of memory to hold items in the stack.

In general, a recursive function has at least two parts: a base condition and at least one recursive case.

Let’s look at a classic example.

# Factorial

`const factorial = function(num) {`

debugger;

if (num === 0 || num === 1) {

return 1

} else {

return num * factorial(num - 1)

}

}factorial(5)

Here we are trying to find 5! (five factorial). The factorial function is defined as the product of all positive integers less than or equal to its argument.

The first condition states: “if the parameter passed equals 0 or 1, we will exit and return 1”.

Next, the recursive case states:

“If the parameter is not 0 or 1, then we will pass value of `num`

times the return value of calling this function again with `num-1`

as its argument”.

So if we call `factorial(0)`

, the function returns 1 and never hits the recursive case.

The same holds for `factorial(1)`

.

We can see what is happening if we insert a debugger statement into the code and use devtools to step though it and watch the call stack.

- The execution stack places
`factorial()`

with 5 as the argument passed. The base case is false, so enter the recursive condition. - The execution stack places
`factorial()`

a second time with`num-1`

= 4 as argument. Base case is false, enter recursive condition. - The execution stack places
`factorial()`

a third time with`num-1`

(4–1) = 3 as argument. Base case is false, enter recursive condition. - The execution stack places
`factorial()`

a fourth time with`num-1`

(3–1) = 2 as argument. Base case is false, enter recursive condition. - The execution stack places
`factorial()`

a fifth time with`num-1`

(2–1) = 1 as argument. Now the base case is true, so return 1.

At this point, we have decreased the argument by one on each function call until we reach a condition to return 1.

6. From here the last execution context completes, `num === 1`

, so that function returns 1.

7. Next `num === 2`

, so the return value is 2. (1×2).

8. Next `num === 3`

, sothe return value is 6, (2×3).

So far we have 1×2×3.

9. Next, `num === 4`

, (4×6). 24 is the return value to the next context.

10. Finally, `num === 5`

, (5×24) and we have 120 as the final value.

Recursion is pretty neat, right?

We could have done the same thing with a for or a while loop. But using recursion yields an elegant solution that is more readable.

This is why we use recursive solutions.

Many times, a problem broken down into smaller parts is more efficient. Dividing a problem into smaller parts aids in conquering it. Hence, recursion is a divide-and-conquer approach to solving problems.

- Sub-problems are easier to solve than the original problem
- Solutions to sub-problems are combined to solve the original problem

“Divide-and-conquer” is most often used to traverse or search data structures such as binary search trees, graphs, and heaps. It also works for many sorting algorithms, like quicksort and heapsort.

Let’s work through the following examples. Use devtools to get a conceptual grasp of what’s happening where and when. Remember to use debugger statements and step though each process.

# Fibonacci

`const fibonacci = function(num) {`

if (num <= 1) {

return num

} else {

return fibonacci(num - 1) + fibonacci(num - 2)

}

}

fibonacci(5);

# Recursive arrays

`function flatten(arr) {`

var result = []

arr.forEach(function(element) {

if (!Array.isArray(element)) {

result.push(element)

} else {

result = result.concat(flatten(element))

}

})

return result

}flatten([1, [2], [3, [[4]]]]);

# Reversing a string

`function reverse(str) {`

if (str.length === 0) return ''

return str[str.length - 1] + reverse(str.substr(0, str.length - 1))

}reverse('abcdefg');

# Quicksort

`function quickSort(arr, lo, hi) {`

if (lo === undefined) lo = 0

if (hi === undefined) hi = arr.length - 1 if (lo < hi) {

// partition the array

var p = partition(arr, lo, hi)

console.log('partition from, ' + lo + ' to ' + hi + '=> partition: ' + p)

// sort subarrays

quickSort(arr, lo, p - 1)

quickSort(arr, p + 1, hi)

}

// for initial call, return a sorted array

if (hi - lo === arr.length - 1) return arr

}function partition(arr, lo, hi) {

// choose last element as pivot

var pivot = arr[hi]

// keep track of index to put pivot at

var pivotLocation = lo

// loop through subarray and if element <= pivot, place element before pivot

for (var i = lo; i < hi; i++) {

if (arr[i] <= pivot) {

swap(arr, pivotLocation, i)

pivotLocation++

}

}

swap(arr, pivotLocation, hi)

return pivotLocation

}function swap(arr, index1, index2) {

if (index1 === index2) return

var temp = arr[index1]

arr[index1] = arr[index2]

arr[index2] = temp

console.log('swapped' + arr[index1], arr[index2], +' in ', arr)

return arr

}quickSort([1, 4, 3, 56, 9, 8, 7, 5])

# Conclusion

Practicing recursive techniques is important. For nested data structures like trees, graphs, and heaps, recursion is invaluable