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 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 n times.
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.
Iterative vs. Recursive
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 for keyword or any of the other ways we wrote repeating code before- while, map, etc. or we'll refer to the loop as recursive- using a function that calls itself.
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!
Rules of Recursive Functions so Far
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.
Rules of Recursive Functions so Far
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.
Reverse a String - Iterative
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!
Reverse a String - Recursive
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!
Full Commentary Version
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!
Compact Refactor
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!
Gather Values
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.
Rules of Recursive Functions so Far
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
Iterative Linked List
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!
Recursive Printing of LL
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
Iterative 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!
Recursive Find Length
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!
Full Commentary Recursive Length
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
Iterative 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!
Recursive Adding to End
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.See here for useful keyboard shortcuts in Repl.
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.​RA Solution Code​
2.​FTBC3 Solution Video​
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.
1.​https://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method​
Further Reading
https://towardsdatascience.com/finding-a-recursive-solution-184784b0aea0
FreeCodeCamp's Intro to Recursion: https://www.freecodecamp.org/news/quick-intro-to-recursion/​
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/​

Algorithms - Previous

A.8: Object-Oriented Programming

A.9.1: Recursive Backtracking

Last modified 1mo ago

Copy link

Contents

Introduction

Background on Recursion

Example - Simple Loops

Example - Base Cases

Example - Return Values

Examples - Linked List

Exercises

Optional Reading