Recursion

Projected Time

About 6 hours

Prerequisites

Motivation

Recursion is a powerful technique you can use to solve certain types of problems, usually those that involve hierarchical data. It is also a common interview subject area.

Objectives

Apprentices will be able to:

Specific Things to Learn

Common Misconceptions

Materials

Techtonica Definition

Example

Summing an array. a = [1,2,3,5,6,7,8]

function sumArray(arr) { let sum = 0; for (let i = 0; i < arr.length; i++) { sum += arr[i]; } return sum; }

You could loop through each number and add them to a running total and then return it. That would be the iterative solution.

The recursive solution would instead say:

This might seem almost silly. Why would you reduce it in this way? But it’s an incredibly powerful technique, for some reasons:

function recursiveSum(arr) { if (arr.length === 1) { return arr[0]; // Base Case } else { const halfwayPoint = Math.floor(arr.length / 2); const firstHalf = arr.slice(0, halfwayPoint); const secondHalf = arr.slice(halfwayPoint, arr.length); return recursiveSum(firstHalf) + recursiveSum(secondHalf); } }

Resources

Supplemental Materials

Lesson

Things to Remember

Demonstration

The instructor demonstrates in the video walkthrough an example of a recursive algorithm in JavaScript.

Independent Practice

Write a recursive function isPalindrome(aString) that returns true if aString is a palindrome. A palindrome is any string that is the same read forwards or backwards: 

isPalindrome('racecar') -> true
isPalindrome('step on no pets') -> true
isPalindrome('a') -> true
isPalindrome('goat') -> false

Challenges

[Challenge] - Factorial

The factorial of a whole number n is written n! and defined as the product of all positive whole numbers less than or equal to n.

For example, the value of 3! (read: three factorial) is 6 which is calculated by multiplying together all whole numbers less than or equal to 3:

factorial(3) = 3! = 3 * 2 * 1 = 6

The value of 10 factorial, for example, can be calculated by:

10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1

Write a function that uses recursion to calculate the factorial of a number.

[Challenge] - Fibonacci

The Fibonacci sequence appears in unexpected places all over mathematics and nature. It is defined by the following three rules:

For example, the first few numbers in the Fibonacci sequence are:

1, 1, 2, 3, 5, 8, 13, 21, ...

The next Fibonacci number is:

13 + 21 = 34

Write a method fib(n) that calculates the nth Fibonacci number (starting from n = 1).

[Challenge] - GCD

The GCD of two or more integers, none of which are zero is the largest positive integer that divides each of the integers. The greatest common divisor(GCD) is also known as:

For example:

the GCD of 48 and 14 is 2.

Pseudocode to calculate GCD of two numbers:
GCD(x, y)
Begin
    if y = 0 then
        return x;
    else
        Call: GCD(y, x%y);
    endif
End

[Challenge] - Tree Operations (Optional Additional Practice)

Consider a fictitious hierarchical organization that looks like follows:

A diagram describing a (fictitious) hierarchical organization in the form of an n-ary tree.
A diagram describing a (fictitious) hierarchical organization in the form of an n-ary tree.

It’s a simple reporting structure, but we can do many interesting things with it. The data structure to represent each node on this tree can be simply expressed as follows:

class Employee {
    constructor(name, title, directReports=[]) {
        this.name = name
        this.title = title
        this.directReports = directReports
    }
}

The very first thing you’d want to do is to starting building the object in your code that would accurately represent the hierarchy in the diagram. Here’s a small sample of what would be needed:

let donnaMeagle = new Employee("Donna Meagle", "Permits Manager");

let jerryGergich = new Employee("Jerry Gergich", "Mindless Factotum");

let ronSwanson = new Employee("Ron Swanson", "Parks Department Head", [donnaMeagle, jerryGergich]);

Build the entire hierarchy of employees first, and then write functions on the Employee class that would:

  1. Give you the total number of reports (both direct and indirect) for any given employee. For the given diagram, getTotalReportsCount() on Chris Traeger should return 8.

  2. Give you all the reports (both direct and indirect) for any given employee. For the given diagram, getAllReports() on Chris Traeger should return an array of employee objects for Ben Wyatt, Ann Perkins, Ron Swanson, April Ludgate, Jerry Gergich, Tom Haverford, Craig Middlebrooks, and Donna Meagle.

Check for Understanding

Given the following code:

int fun1(int x, int y)
{
  if(x == 0)
    return y;
  else
    return fun1(x - 1,  x + y);
}

What do these function calls return? fun1(1, 1) fun1(2, 1) fun1(2, 2) fun1(0, 2)

And remember: always have a base case

Note: You can get this on a T-shirt