Recursion

Learning Goals

• Understand the concept of recursion
• Understand the limitations of recursion in JS & Ruby
• Be able to solve problems using recursion
• Know the theory behind Tail Call Optimization

Reviewing Key Concepts

Recursion is an important programming technique in which a function CALLS ITSELF. Yes, you read that right.

More specifically, a recursive function is a function that calls itself until it arrives at a final result.

The anatomy of a recursive function

Every recursive function (reminder, just a function that calls itself) must have these two pieces:

1. A simple base case (or cases): a terminating scenario that does not use recursion to produce an answer
   • Often written as an if statement
   • Think of this as similar to the test condition in a for loop - under what condition do we want to STOP recursively calling the function?
   • Without a base case (like a loop without a valid test condition) we will end up recursively calling the function FOREVER… or until we get a stack overflow error.
2. A recursive case: A set of instructions, moving closer towards the base case, that ends in a call to the same function

Let’s see this in action with a function that takes a number as an argument and counts down to zero. You can clone down this js repo and this ruby repo to use as sandboxes for the practice exercises found throughout this lesson.

Javascript Prompt

 countdown( 3 );
 // We want this function to countdown from the starting number until we get to 0
 // 3
 // 2
 // 1
 // 0

Psuedocode

 const countdown = number => {
   //base case - when do we want to stop?
     //stop when we get to zero (0)
   //recursive case
     //print the number we are currently on
     //call the countdown function again with the next number
 }

 const countdown = number => {
   // check our base case, if statement
   if (!number) {
     return 0;
   }
  
   console.log(number);

   // recursive case moving towards base case
   return countdown(number - 1)
 }

 countdown(3); // 3, 2, 1, 0

Ruby Prompt

countdown(3)
# We want this function to countdown from the starting number until we get to 0
# 3
# 2
# 1
# 0

Psuedocode

def countdown(num)
  # base case - when do we want to stop?
    # stop when we get to zero (0)
  # recursive case
    # print the number we are currently on
    # call the countdown function again with the next number
end

def countdown(num)
  # check our base case, if statement
  if num < 0
    return
  end
  
  p num
  
  # recursive case moving towards base case
  countdown(num - 1)
end

Advantages

• Allows you to break problems down into the smallest, most repeatable step and do that small step over and over!
• Useful for iterative branching including:
  • fractal math
  • sorting
  • traversing nodes of complex/non-linear structures (binary or prefix tries)
• Recursion is more functional in that it doesn’t keep track of state (no side effects)

Disadvantages

• Recursion is not optimized in many languages including JS & Ruby
  • Execution contexts continue to get built on the callstack.
  • With bigger datasets, this can be a problem.
    • Memory consumption can lead to the maximum call stack size being exceeded.
    • Loops on the otherhand don’t need to add functions to the call stack. (better memory management)

Diving Deeper Into The Process

Let’s work through one more together and write out a function that takes in an argument of an array of numbers and adds them together.

Javascript Setup

let numbers = [ 1, 2, 3, 4 ];

getSum(numbers); // 10

Ruby Setup

  numbers = [1,2,3,4]
  
  get_sum(numbers)
  # => 10

One of the most basic patterns of recursion is when you can reduce a problem to a smaller one and then keep reducing until you can’t do it anymore. This is also known as natural recursion.

So, at the most basic level, we just want to add one number with another number! How might this look in psuedocode? (Try it on your own first, then check out the pseudocode below.)

  //base case
    //if there are no more numbers to add, return 0
  //recursive case
    //take the first number from the nums array
    //add that number to the result of calling getSum with the remaining numbers

It can be helpful to break down what each step of this problem looks like. Here’s one way to visualize the call stack:

const getSum = nums => {
  // base case
  if (!nums.length) {
    return 0;
  }
  
  // get closer to base case
  let firstNumber = nums.shift();
  
  return firstNumber + getSum(nums);
}

 def get_sum(nums)
  # base case
  if nums.empty?
    return 0
  end
  
  # get closer to base case
  first_number = nums.shift
  
  first_number + get_sum(nums)
 end

Exercises

The best way to start understanding recursion is to just try doing it! Feel free to work through these problems in either JavaScript or Ruby.

5 x 4 x 3 x 2 x 1 = 120

// create a function which takes a string of characters and
// recursively calls itself to reverse the string

// e.g.

let reversedString = reverse('Ariel')

console.log(reversedString); // leirA

// create a function which takes a number and an exponent and
// recursively calls itself to calculate the product

// e.g.
let base = 2;
let exponent = 4;
let product = power(base, exponent)  // 2 to the 4th power

console.log(product);  // 16

// create a function which takes a string
// and recursively calls itself to determine if the string is palindrome

// e.g.

console.log(isPalindrome('racecar'));  // true
console.log(isPalindrome('a')); //true
console.log(isPalindrome('library'));  // false
console.log(isPalindrome('dngojkafnghkoasng'));  // false

Tail Call Optimization

We won’t work through this section in the lesson today. Tail Call Optimization is something to dig into yourself if you’re curious. Note that neither Ruby nor JavaScript natively supports tail call optimization (TCO) out of the box so this may be a nice-to-know more than something you’ll actually be able to implement depending on the environment you’re working in.

Recursion isn’t really optimized for JS or Ruby. By adding to the call stack with each recursive call, this can become too much to handle for recursive functions using large datasets! To get around the stack overflow issue, one can use tail call optimization. A tail call refers to the last action that is executed. In this scenario, the recursive call must be the last statement of the recursive function.

Let’s think back to our getSum function we wrote earlier…

// Example:
// Create a getSum fn that adds all of the numbers in an array

// Example that is not optimized due to it returning an operation
return firstNumber + getSum(nums);

// Example suited for tail call optimization
return getSum(nums, sum + firstNumber);

Notice with the first example, we are returning an operation. In this scenario, this would need to be added to the callstack because this cannot be executed until we know what getSum(allNumbers) returns.

In the second example, we are only returning the recursive function and passing what arguments we need to keep track of the sum, making this perfect for Tail Call Optimization so that it can execute immediately instead of stacking in memory. Taking what we understand from this, let’s make some adjustments to the solution we just worked through!

const getSum = (nums, sum=0) => {
  // base case
  if (!nums.length) {
    return sum;
  }
  
  // get closer to base case
  let firstNumber = nums.shift();
  
  return getSum(nums, sum + firstNumber);
}

Note that for Javascript, this optimization is only available in Safari. (Chrome, FireFox, and other browsers are not optimized currently). Read here to understand more of the history about this.

In Ruby, this optimization is not available by default. You can configure the Ruby compiler to enable tail call optimization however. If you’re interested, follow the article here!

Bonus

Now try and solve these problems with tail call optimization!