- What is recursion?
- What cases do I need to think about?
- Can you think of an example of when to use recursion?
- How do you avoid infinite recursion?
- What is the structure and definition of a recursive algorithm?
- What is the Base case?
- What is the Recursive case?
- JavaScript 1 - Variables, Strings, Numbers
- JavaScript 2 - Arrays, Functions
- JavaScript 3 - Conditionals, Comparisons, Booleans
- JavaScript 4 - Loops
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.
- Interview Questions!
- Fibonacci sequence
- Factorial
- Tree traversal
Participants will be able to:
- Understand the structure and definition of a recursive algorithm
- Distinguish between iterative and recursive functions
- Recognize problems where recursion would be a good solution
- Solve coding challenges using recursion
- Video walkthrough of lesson slides Recursion video (12 mins watch)
- Read through lesson slides Recursion
- Watch video Recursion: Russian Nesting Dolls (5 mins watch)
- Watch FunFunFunction - Recursion - Part 7 of Functional Programming in JavaScript video (16 mins watch) - Learn from Matthias about recursion.
- A recursive function is any function that calls itself.
- (Recursion refers to the process of evaluating a recursive function)
- Recursion is usually contrasted with iteration, the process of solving a problem by a single function, called once, that solves the problem in its entirety
- Recursive solutions tend to divide a larger problem (or data set) into smaller pieces, often further and further, until the logic can seem trivial (adding two numbers or check if a == b)
- Recursive solutions tend to be short and sweet, which means you have to think about them for a bit to follow along, unlike an iterative solution that might be easier to read
The sum of an array of integers
//Iterative approach to calculate sum
function sumArray(arr) {
let sum = 0;
//Add each array element to sum variable
for (let i = 0; i < arr.length; i++) {
sum += arr[i];
}
//return final result
return sum;
}
let arr = [1, 2, 3];
console.log(sumArray(arr)); // 6You 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:
function sumArray(array) {
// Base case
if (array.length === 0) {
return 0;
// Recursive case
} else {
return array[0] + sumArray(array.slice(1));
}
}
let array = [1, 2, 3];
console.log(sumArray(array)); // 6-
array.length === 0is our base case. When array is empty, function should return zero -
return array[0] + sumArray(array.slice(1))is where the recursion magic happens. Here we are callingsumArray()function itself. array.slice(1) creates a shallow copy of an array starting from the first element onwards, and no mutation ever occurs on the original array.1
Let's break it down line by line.
// recursive case
sumArray([1,2,3]) return 1 + sumArray([2,3])
// recursive case
sumArray([2,3]) return 1 + 2 + sumArray([3])
// recursive case
sumArray([3]) return 1 + 2 + 3 + sumArray([])
// base case
sumArray([]) return 1 + 2 + 3 + 0
- You can solve all recursion problems with a while loop and vice versa
- Recursion solutions are usually simpler to implement and easier to read
- Recursive algorithms are often used to solve problems with the Tree data structures (for example, the DOM is a tree!)
- Myth: Recursion is only used in Computer Science classes and in interviews. Real Code™ doesn't use it.
- This is 100% untrue
- Operations on the DOM (a tree structure) often involves recursion
- Other hierarchical data structures are natural fits for recursive algorithms (filesystems, lists of lists, any graph)
- Recursion is inefficient.
- (Often the reason cited for why Real Code™ doesn't use it)
- Recursive code is compact because it's essentially using the call stack as a built-in data structure. However, this structure has a cost. So on the one hand, this is not a myth. However if your call stack can fit in memory, why not use this elegant tool?
- Also Pro Tip: Performance of in-memory code is usually largely irrelevant. System scaling bottlenecks in the real world usually relate to databases and other forms of latency. Unlike Computer Science students, professional engineers usually favor simpler code that is easier to understand later than squeezing every last byte from an algorithm.
- "The real problem is that programmers have spent far too much time worrying about efficiency in the wrong places and at the wrong times; premature optimization is the root of all evil (or at least most of it) in programming." –Donald Knuth
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
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.
The Fibonacci sequence appears in unexpected places all over mathematics and nature. It is defined by the following three rules:
- The first Fibonacci number is 1
- The second Fibonacci number is 1
- Every other Fibonacci number is the sum of the previous two Fibonacci numbers
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 thenth Fibonacci number (starting fromn = 1).
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:
- the greatest common factor (GCF),
- highest common factor (HCF),
- greatest common measure (GCM),
- highest common divisor.
For example:
the GCD of 48 and 14 is 2.
GCD(x, y)
Begin
if y = 0 then
return x;
else
Call: GCD(y, x%y);
endif
End
Consider a fictitious hierarchical organization that looks like follows:
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:
-
Give you the total number of reports (both direct and indirect) for any given employee. For the given diagram,
getTotalReportsCount()on Chris Traeger should return8. -
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.
Given the following code:
function fun1(x, 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)
Note: You can get this on a T-shirt