Bootcamp

Search…

📅

Course Schedule

🛠

Course Logistics

🏞

Projects

0: Language and Tooling

1: Frontend Basics

🌈

CSS

2: Backend Basics

3: Backend Applications

4: Backend Structure

5: Full-Stack Applications

6: Frontend Infrastructure

7: React

8: Advanced React

9: Advanced Topics

🧮

Algorithms

💼

Interview Prep

☺

User Experience

0: Language and Tooling Teaching Guide

1: Frontend Basics Teaching Guide

🌈

CSS Teaching Guide

2: Backend Basics Teaching Guide

3: Backend Applications Teaching Guide

4: Backend Structure Teaching Guide

5: Full-Stack Applications Teaching Guide

6: Frontend Infrastructure Teaching Guide

7: React Teaching Guide

8: Advanced React Teaching Guide

9: Advanced Topics Teaching Guide

🧮

Algorithms Teaching Guide

💼

Interview Prep Teaching Guide

☺

User Experience Teaching Guide

A.9: Recursion

Introduction

For solving certain types of algorithm problems we'll want to repeat an action several times, as in a loop- the syntax keyword *n* times.

`for`

in JavaScript and Python. There is another syntax to repeat some code a set number of times called recursion. Recursion is a function that calls itself. Specifically we we need to add some features inside the function so that it stops after We'll see through some examples where a given concept or code is expressed more elegantly (not necessarily more simply) in the format of a function that calls itself. This may be preferable to writing the code using the

`for`

keyword to make a loop.1

def say_something

2

print("hello")

3

say_something() # keep repeating this function forever

Copied!

New Vocabulary for Loops

When we introduce this new syntax for repeating some code with a function that calls itself, we'll still call that a loop, but make a new distinction between what kind of loop it is.

From now on we'll refer to writing "loops" (code that repeats a given number of times) either as *iteratively*, that is using something like the **or** we'll refer to the loop as *recursive*- using a function that calls itself.

`for`

keyword or any of the other ways we wrote repeating code before- `while`

, `map`

, etc. Recursive Vocabulary

There are 2 concepts to remember with recursion.

- 1.Recurrence relation
- 1.When our function calls itself, what do we expect to be returned by that function?

- 2.Base case
- 1.When does our function stop calling itself and return a value that does not depend on the function calling itself again?
- 2.In our Fibonacci example, our base cases would be that
`Fib(0) == 1`

and`Fib(1) == 1`

. - 3.Without base cases, our recursive function would recurse infinitely and result in an infinite loop.

Background on Recursion

The history of recursion is deeply tied to the invention of Turing's theoretical computer. The word recursion is not just a topic in Computer Science but also a topic in mathematical logic. So the concept of recursion is deeper than simply a function that calls itself. It is any construct or system that is defined in terms of itself. Implementations of the concept of recursion include a JavaScript interpreter written in JavaScript, or a quine, a program whose purpose is to print out it's own code. However, the purposes of Rocket's algorithms content we can assume the word recursion to mean a loop.

Example - Simple Loops

Infinite Recursive Loop

Given this infinite iterative loop:

1

count = 0

2

while True:

3

print(f'count: {count}')

4

count += 1

Copied!

Let's implement the same loop in recursion.

1

def loop_count_times(count: int) -> None

2

print(f'count: {count}')

3

new_count = count + 1

4

loop_count_times(new_count)

5

6

loop_count_times(0) # start the loop at zero, will increase forever

Copied!

- 1.Function must call itself

Example - Base Cases

The first important property of recursion that must be implemented is the "base case". This simply means the condition for stopping what would otherwise be the infinite recursing loop.

In a function context the base case always has to do with the function returning or not. A base case that satisfies the base condition can return, or exit out of that recursive call.

Base Case - How to End the Loop

Given this iterative loop:

1

count = 5

2

while count != 0:

3

print(f'count: {count}')

4

count -= 1

Copied!

Let's implement the same loop in recursion.

1

def loop_count_times(count: int) -> None

2

print(f'count: {count}')

3

if count == 0:

4

return

5

new_count = count - 1

6

loop_count_times(new_count)

7

8

loop_count_times(5)

Copied!

On line 3 s the Base Case. We need to be able to write code that, in contrast to the infinite example above, knows when to end the loop.

Note that as the function gets called over and over again we can define function calls 3,4 and 5 as dealing with an ever-reducing set of data.

- 1.Function must call itself
- 2.Must have a base case to say when to stop.
- 3.Called with a smaller piece of the original data every "iteration".

Base Case with Parameters

How can we implement a recursive loop that counts up instead of down?

Given this iterative loop:

1

count = 0

2

while count < 5:

3

print(f'count: {count}')

4

count += 1

Copied!

Let's implement the same loop in recursion.

1

def loop_count_times(max: int, count: int) -> None

2

print(f'count: {count}')

3

if count == max:

4

return

5

new_count = count + 1

6

loop_count_times(max, new_count)

7

8

loop_count_times(5,0)

Copied!

Also note that it is a convention to have the base case at the top of the function. We actually call the function at the end once just to check the count value and return / end the loop, even though it isn't affecting the counter- it will just end after the check fails.

Example - Return Values

So far having a base case condition that exits the loop is relatively simple. Now we'll look at functions that return a value. This turns out to make tracking the execution of the recursive function much, much more difficult. When first learning about recursion this tracing of the execution context is one of the main difficulties.

This exposes the other major behaviour of a recursive function that returns a value: each step of the function deals with a smaller and smaller piece of the data. The return value of the function builds that data back up piece by piece.

How do we write recursive functions that returns values?

Demonstration of recursive string reverse from here: https://towardsdatascience.com/finding-a-recursive-solution-184784b0aea0

Given this iterative loop:

1

def reverse_iter(word: str) -> str:

2

result = ''

3

for char in word:

4

result = char + result

5

return result

6

7

result = reverse_iter('hello') # olleh

Copied!

Let's implement the same loop in recursion.

1

def reverse_recurse(word: str) -> str:

2

3

if len(word) == 0:

4

return ''

5

6

last_letter = word[-1] # letter at the end of the word

7

rest = word[:-1] # the rest of the string except the last letter

8

9

# get the result of reversing every other letter before the current one

10

recurse_result = reverse(rest)

11

12

new_string = last_letter + recurse_result # arrange the last letter in front

13

14

return new_string

15

16

result = reverse_recurse('hello') # olleh

Copied!

Run this version and follow the call stack to see where each part of the function branches off to recurse and comes back.

1

def reverse_recurse(string: str) -> str:

2

print(f'current word: {string}')

3

4

if len(string) == 0:

5

print('========== reached the base case')

6

return ''

7

8

last_letter = string[-1] # letter at the end of the string

9

rest = string[:-1] # the rest of the string except the last letter

10

11

print(f'^^^ about to recurse. this is rest: {rest}')

12

# get the result of reversing every other letter before the current one

13

recurse_result = reverse_recurse(rest)

14

15

print(f"### we're back. this was string function param: {string}")

16

17

new_string = last_letter + recurse_result # arrange the last letter in front

18

19

print(f'recurse result: >> {recurse_result} <<')

20

print(f'putting last letter on first: {last_letter}')

21

22

return new_string

23

24

result = reverse_recurse('hello') # olleh

25

print(f'reverse result: {result}')

Copied!

The common style of recursive functions is to write all of the intermediate values inline with the return.

1

def reverse_recurse_compact(word: str) -> str:

2

if len(word) == 0:

3

return ''

4

else:

5

return word[-1] + reverse_recurse_compact(word[:-1])

6

7

result = reverse_recurse_compact('hello')

Copied!

The key to understanding the control flow of this function is to understand that the values are gathering back up and the function returns back to what will become

`result`

. Our final goal is to have the accumulated total value inside of `result`

- each time we get a new return value we get to put together another piece of the answer.- 1.Function must call itself
- 2.Must have a base case to say when to stop.
- 3.Called with a smaller piece of the original data.
- 4.Function return values accumulate previously gathered values, our recursive function must compile these values.

Examples - Linked List

A nice way to see how recursion applies to code we might write is to look at converting some code that we had previously written as iterative. One ongoing challenge will be to understand what makes a given problem appropriate for a recursive solution or not. Many propblems ca be written either way. In these ideal conversions between iterative and recursive try to see how the paradigm of "repeat the sme action (function) over and over again for a constantly reducing set of data" applies to these linked list examples.

Print Out Values

We can write certain linked list methods as recursive insterad of iterative.

Given a normal linked list class:

1

class Node:

2

def __init__(self, value):

3

self.value = value

4

self.nextnode = None

Copied!

We can put values inside the list:

1

head = Node(1)

2

head.nextnode = Node(2)

3

head.nextnode.nextnode = Node(3)

4

head.nextnode.nextnode.nextnode = Node(4)

5

head.nextnode.nextnode.nextnode.nextnode = Node(5)

6

head.nextnode.nextnode.nextnode.nextnode.nextnode = Node(3)

7

head.nextnode.nextnode.nextnode.nextnode.nextnode.nextnode = Node(3)

Copied!

1

def display_ll(node):

2

while node:

3

print(node.value, end=" --> ")

4

node = node.nextnode

5

print(None)

6

7

display_ll(head) # 1 --> 2 --> 3 --> 4 --> 5 --> 3 --> 3 --> None

Copied!

We can write the same LL algorithm recursively:

1

def display_ll_recursive(node):

2

3

if node == None:

4

return

5

6

print(node.value, end=" --> ")

7

display_ll_recursive(node.nextnode)

8

9

display_ll_recursive(head) # 1 --> 2 --> 3 --> 4 --> 5 --> 3 --> 3 --> None

Copied!

This code gives a hint that some kinds of algorithms are more elegantly expressed in terms of recursion.

Recursive Find Length

This slight modification on the above would find the length of the list:

1

def length(node):

2

length=0

3

while node:

4

length += 1

5

node = node.nextnode

6

7

result = length(head)

8

print(result)

Copied!

Now we can modify the above recursive function to return the list length:

1

def length_recursive(node):

2

3

if node == None:

4

return 0

5

6

return length_recursive(node.nextnode) + 1

7

8

result = length_recursive(head)

9

print(result)

Copied!

Follow the comments to see where the return values recurse down and back up, so that a value can be returned

1

def length_recursive(node):

2

3

if node == None:

4

print(f"### we're going back. this is None")

5

return 0

6

7

print(f'recursing down. node value is: {node.value}')

8

accumulated_length = length_recursive(node.nextnode)

9

print(f'we got a return value. current length is: {current_length}')

10

11

current_node_count = 1

12

current_total = current_node_count + accumulated_length

13

14

print(f"we got a return value. current total is: {current_total}")

15

16

return current_total

17

18

result = length_recursive(head)

19

print(result)

Copied!

Adding to End

Given this iterative way to find the end of the list and add a node:

1

def add(node, newnode):

2

''' Adds a new node object at the end of the ll '''

3

# Go to the end of the existing LL

4

while node:

5

# Keep track of the last node with prevnode

6

prevnode = node

7

node = node.nextnode

8

# Attach newnode to the final prevnode

9

prevnode.nextnode = newnode

10

11

add(head, Node(3))

12

display_ll(head)

Copied!

This can also be implemented using recursion:

1

def addRecursive(node, newnode):

2

''' Adds a new node object at the end of the ll '''

3

if (node == None):

4

return newnode

5

else:

6

node.next = addRecursive(node.nextnode, newnode)

7

return node

8

9

addRecursive(head, Node(3))

10

display_ll(head)

Copied!

Exercises

Instructions

We will be working through these exercises over multiple days. Please see your batch schedule for which exercises to do on which days.

We will complete the Learn Python Recursion Repl. Please start with this empty starter repl. RA created this repl by copying the @Learnpython Recursion Repl and removing answers.

- 1.Pressing the Play button (
`Ctrl+Enter`

on Windows,`Cmd+Enter`

on Mac) in Repl to run`main.py`

will execute all problems against the provided test cases. - 2.To limit the problems that Repl executes at any given time, see instructions in the Repl document to edit the
`problems`

array in the`main`

function. - 3.

Reference Solutions

Please attempt to solve each problem on your own before reviewing each problem's answer. If you find yourself stuck and unable to proceed, feel free to learn from sample answers for each problem in the @Learnpython Recursion Repl. Note there are multiple ways to solve each problem and the sample answers represent only 1 way.

Part 1

- 1.Factorial
- 2.Bunny Ears
- 3.Fibonacci
- 4.Bunny Ears 2
- 5.Triangle
- 6.Sum Digits
- 7.Count 7
- 8.Count 8
- 9.Power N
- 10.Count X
- 11.Count Hi

Part 2

- 1.Change XY
- 2.Change Pi
- 3.No X
- 4.Array 6
- 5.Array 11
- 6.Array 220
- 7.All Star
- 8.Pair Star
- 9.End X
- 10.Count Pairs

Part 3

- 1.Count ABC
- 2.Count 11
- 3.String Clean
- 4.Count Hi 2
- 5.Paren Bit
- 6.Nest Paren
- 7.Str Count
- 8.Str Copies
- 9.Str Dist
- 1.

Optional Reading

- 1.Fast Exponentiation. What would be the time complexity of an algorithm to calculate the value of
`2^n`

, where`n`

is an input value? A naïve solution would be to write a for loop to multiply 2 by itself`n`

times, which would run in`O(n)`

time complexity. However, if we take the notion that`2^2^2 == 2^4`

, and`2^4^2 == 2^8`

, we can see that we can calculate`2^n`

in many fewer operations than`n`

, on the order of`log(n)`

, with time complexity of`O(logn)`

. Fast exponentiation can be implemented relatively easily with recursion. Programming languages typically implement exponent operators using fast exponentiation.

Further Reading

https://towardsdatascience.com/finding-a-recursive-solution-184784b0aea0

https://www.youtube.com/watch?v=AfBqVVKg4GE

https://www.youtube.com/watch?v=mz6tAJMVmfM

Stanford's Intro to Recursion: https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1206/lectures/intro-to-recursion/

Last modified 1mo ago