by Kevin Turney

Recursion is not hard: a step-by-step walkthrough of this useful programming technique

I’m going to say this right off the bat. Do you know the events that happen upon function invocation? No? Then that’s where we will start.

Function invocation

When we call a function, an execution context gets placed on the execution stack. Let’s break this down some more.

First, what is a stack?

A stack is a data structure that operates on a “Last In, First Out” basis. An item is “pushed” onto a stack to add to it, and an item is “popped” off the stack to remove it.

Using a stack is a method of ordering certain operations for execution.

Now, back to what is an execution context? An execution context forms upon a function invocation. This context places itself on an execution stack, an order of operations. The item that is always first in this stack is the global execution context. Next up are any function created contexts.

These execution contexts have properties, an Activation Object and a “this” binding. The “this” binding is a reference back to this execution context. The Activation Object includes: parameters passed, declared variables, and function declarations.

So every time we place a new context on the stack, we usually have everything we need to execute code.

Why do I say usually?

With recursion, we are waiting for return values coming from other execution contexts. These other contexts are higher up the stack. When the last item on the stack finishes execution, that context generates a return value. This return value gets passed down as a return value from the recursive case to the next item. That execution context is then popped off the stack.

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])

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

In a future article, I will discuss tail-call optimization and memoization techniques as they relate to recursion. Thanks for reading!

Further resources

Wikipedia

Software Engineering

Another good article

M.I.T. open courseware