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.

1. The execution stack places factorial() with 5 as the argument passed. The base case is false, so enter the recursive condition.
2. The execution stack places factorial() a second time with num-1 = 4 as argument. Base case is false, enter recursive condition.
3. The execution stack places factorial() a third time with num-1 (4–1) = 3 as argument. Base case is false, enter recursive condition.
4. The execution stack places factorial() a fourth time with num-1(3–1) = 2 as argument. Base case is false, enter recursive condition.
5. 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