# A.4: Recursion

## Learning Objectives

Recursion is a function calling itself

All recursive problems can be solve iteratively and vice versa, but certain problems are more easily solved with either recursion or iteration

All recursive functions have 1 or more recurrence relations and 1 or more base cases

We can use call stack diagrams to visualise recursive function calls

Recursive backtracking is a technique used to explore problem spaces

Our recursive functions either return values that "add up" to a final result, or store results in a variable outside the recursive function call

## Introduction

Recursion means a function calling itself. Certain classes of algorithm problems, especially those involving trees, graphs and dynamic programming are easier solved with recursion than with iteration (i.e. loops).

Take the Fibonacci problem for example, where our goal is to find `fib(n)`

where `fib(n)`

is defined as `fib(n-1) + fib(n-2)`

. This is much more easily modelled with recursion than iteration. To model this problem with iteration we would have to calculate how many of each Fib number between 0 and `n`

to add together, which can be challenging.

All problems that can be solved with recursion can also be solved with iteration and vice versa. Sometimes recursive and iterative solutions are equally accessible; sometimes one is much simpler than the other. As we do more recursion problems we will gain intuition for when to use recursion vs iteration.

## Key Concepts

Every recursive function has 2 key components: 1 or more recurrence relations and 1 or more base cases. We can use the function call stack and sometimes even trees (covered in later submodule) to visualise our recursive algorithm.

### Recurrence Relation

Recurrence relations define what we expect our functions to do in relation to themselves, usually passing a subset of data to child functions. For example, the recurrence relation in our Fibonacci example above is the return value `fib(n-1) + fib(n-2)`

. Without worrying what `fib(n-1)`

and `fib(n-2)`

do internally, we expect `fib(n)`

to return `fib(n-1) + fib(n-2)`

, and if `fib(n)`

does that we have solved our problem.

### Base Case

Base cases exist to stop our recursion once they have reached their natural stopping point, for example 0 or the end of a list. Without base cases our recursive functions would recurse infinitely, exhausting the memory and crashing the programs that run them.

In our above Fibonacci example, the base case is when `n === 1`

or `n === 0`

, because the Fibonacci sequence explicitly defines `fib(1)`

as 1 and `fib(0)`

as 0. This prevents our function from recursing infinitely.

### Call Stack

In Colt Steele's video above you may hear him talking about "call stacks" from 10:20 onward, which are an important tool to visualise recursive functions (and program execution in general). Call stacks are like the stacks we learn at Rocket, except for function calls. Every time JavaScript calls a function, JavaScript pushes that function to its global call stack. When a function calls a nested child function, JavaScript pushes the child function to the call stack. JavaScript pops functions from the call stack when they and their children have finished execution.

Call stacks help us solve recursion problems because they help us visualise the state of our algorithm at any point of execution. Whenever we are stuck on a recursion problem we can always trace our algorithm by drawing a call stack to systematically find our bug.

### Backtracking

Recursive backtracking is a concept in more advanced recursion problems to explore permutations. Backtracking involves making a move, recursively making more moves, then un-making our original move to try a different move if needed. This 3-step process typically happens inside a loop where we loop through possible moves. Backtracking problems include finding string permutations, maze-solving, sudoku puzzles, and simulating chess.

The following video explains how we can use backtracking to find permutations of a string.

## Examples

The following examples explore using recursion with common data types seen in recursion problems. Recursion is also often used with trees, but we will explore that in the trees submodule.

### Numbers: Power of Two

#### Problem

https://leetcode.com/problems/power-of-two/

Given an integer `n`

, return `true`

if it is a power of two. Otherwise, return `false`

. An integer `n`

is a power of two, if there exists an integer `x`

such that `n === 2^x`

.

#### Strategy

At each function call:

If

`n`

is less than 1, return`false`

. This is an edge case that LeetCode throws at us.If

`n`

is 1 or 2, return`true`

. This is our base case. If we continuously divide a number that is a power of 2 by 2, we will eventually get 2. At this point we know we have a power of 2.If

`n/2`

is an odd number, the original`n`

is not a power of 2. Return`false`

.If

`n/2`

is even, return`isPowerOfTwo(n/2)`

. The recurrence relation will determine if the "rest" of the number is a power of 2.

### Strings/Arrays: Letter Tile Possibilities

#### Problem

https://leetcode.com/problems/letter-tile-possibilities/

You have `n`

`tiles`

, where each tile has one letter `tiles[i]`

printed on it. Return *the number of possible non-empty sequences of letters* you can make using the letters printed on those `tiles`

.

#### Strategy

To eliminate duplicates, we store our results in a set (like hash table with only keys) `sequences`

outside of our recursive function calls, and define a helper function `findPossibilities`

inside the given function as our recursive function. `findPossibilities`

recursively finds all possible sequences and adds them to `sequences`

, and in the end we return the number of sequences in `sequences`

.

`findPossibilities`

has the following logic.

If the current sequence is non-empty, add it to

`sequences`

, in case we have not seen it beforeBase case: If there are no letters remaining to add to the current sequence, return

Note because we store results in a variable outside

`findPossibilities`

,`findPossibilities`

does not need to return anything

For each of the remaining tiles

Add that tile to the current sequence

Recursively find all remaining possibilities after adding that tile.

Remove that tile. This is the backtracking step.

`findPossibilities`

systematically explores all options and once it finishes we can return our result.

## Exercises

Problems through Part 1 use relatively vanilla recursion. Problems from Part 2 onward involve recursive backtracking.

After attempting each problem, find solutions in the Leaderboard tab (HackerRank, may be on left side of page) or Solution or Discuss tabs (LeetCode) on that problem's page. If you get stuck for more than 15 minutes, review and understand the solutions and move on. Come back and re-attempt the problem after a few days.

### Pre-Class

Power of Two (LeetCode)

### Part 1

Power of Three (LeetCode)

Power of Four (LeetCode)

Recursive Digit Sum (HackerRank)

### Part 2

Letter Tile Possibilities (LeetCode)

Generate Parentheses (LeetCode)

Hint: Consider this slide on how we can prune invalid subtrees.

Rocket solution code (Python)

Rocket solution video (Python, until 57:25)

Combination Sum (LeetCode)

### Part 3

Combinations (LeetCode)

Hint: Can we use a for loop to generate the first of

`k`

numbers, use a recursive function to generate the remaining`k-1`

numbers, and combine the first and`k-1`

numbers after the recursive call?

Subsets (LeetCode)

Hint: Same strategy as Combinations

### Part 4

Letter Combinations of a Phone Number (LeetCode)

Hint: Same strategy as Combinations

Subsets II (LeetCode)

Hint: Consider using a hash table or JavaScript set to remove duplicates

### Part 5

Last updated