Recursion

Introduction to Software Engineering (CSSE 1001)

Author

Paul Vrbik

Published

May 21, 2026

Recursion

When a function calls itself it is classified as a recursive function.

This may seem strange because we are using the function to define the function but this is logically sound.

Memes

(a) Infinite Recursion
(b) Drake Recursion
(c) Google Recursion
(d) Recursion Meme
(e) Base Case Meme
(f) Understand Meme
Figure 1: Recursion via memes. Click images to make them larger.

Induction

Recursion is essentially an implementation/realization of mathematical induction.

Warning

You will not be tested, nor must you really understand, induction. It is just motivation.

Theorem 1 (The Principle of Mathematical Induction) For any predicate \(P : \mathbb{N} \to \{\text{True}, \text{False}\}\) \[ (P(0) \land (P(n) \implies P(n+1))) \implies \forall m \in \mathbb{N}, P(m) \]

In prose this means: if

  1. the proposition is true for zero, and
  2. if the proposition is true for \(n\) then it is also true for \(n+1\),

then \(P(n)\) is true in general.

Tiling

A standard chess board can be filled with ‘corner-tiles’ so that only one space is left uncovered and no tiles overlap.

Here is one such tiling:

where the disc shows the (arbitrary) location of the uncovered square.

Proposition 1 Any \(2^n \times 2^n\) board with \(n \in \mathbb{N}\) can be tiled so that only one square is left uncovered.

Proof. Base Case We can cover a \(2^0 \times 2^0 = 1 \times 1\) board with zero tiles:

Induction Hypothesis Assume a \(2^n \times 2^n\) board can be tiled.

We can tile a \(2^{n+1} \times 2^{n+1}\) board because, by our assumption, tilings for \(2^n \times 2^n\) board exists.

Recursion Ingredients

Every recursion must have at least one of each of the following.

Base Case: A case which is defined outright (i.e. where the input is so small or simple that we can immediately return the answer without recursing). That is,

if base_case:
    return constant

Recursive Step: A line where the function calls itself on a “smaller” or “simpler” input. The input must be able to move the function call closer to the base case. If a recursive function calls itself on the same input with which it was originally called, it will not be able to reach the base case and will not terminate (infinite recursion).

Without the recursive step, the function is not recursive. Without the base case, the function will not be able to terminate (infinite recursion).

Factorial

The canonical example for a recursive function is the factorial.

Let \(n \in \mathbb{N}\) then the factorial of \(n\), denoted \(n!\) is given by \[ n! = \begin{cases} 1 & \text{when } n = 0\\ n \times (n-1)! & \text{otherwise} \end{cases} \] For instance \(3! = 3 \times 2 \times 1 \times 1 = 6\).

Side-note: A set of \(n\) distinct elements can be arranged in \(n!\) different ways.

def fact(n: int) -> int:
    if not n:             # Pythonic zero check
        return 1          # Base case
    return n * fact(n-1)  # Inductive case/Recursion
fact(0) 
1
fact(3) 
6
fact(-1) 
RecursionError: maximum recursion depth exceeded  # Bottoming out

Winding

Here is how our fact code is evaluated for \(n=4\). \[ \begin{align*} \MoveEqLeft\mbox{factorial}(4) \\ &\gets 4 \times \mbox{factorial}(3)\\ &\gets 4 \times (3 \times \mbox{factorial}(2))\\ &\gets 4 \times (3 \times (2 \times \mbox{factorial}(1)))\\ &\gets 4 \times (3 \times (2 \times (1 \times \mbox{factorial}(0)))) \end{align*} \] This is called the winding phase of the evaluation process.

During the winding phase, new recursive calls build a stack of activation records that complete last in first out.

Note: A stack would be drawn in the reverse order.

Unwinding

After winding we do unwinding. \[ \begin{align*} \MoveEqLeft \mbox{factorial}(4) && \mbox{winding} \\ &\;\;\vdots &&\;\;\;\;\;\vdots \\ &\gets 4 \times (3 \times (2 \times (1 \times \mbox{factorial}(0)))) && \mbox{winding} \\ &\gets 4 \times (3 \times (2 \times (1 \times 1))) &&\mbox{unwinding} \\ &\gets 4 \times (3 \times (2 \times 1)) &&\;\;\;\;\;\vdots \\ &\gets 4 \times (3 \times 2)&&\;\;\;\;\;\vdots \\ &\gets 4 \times 6&&\;\;\;\;\;\vdots \\ &\gets 24 && \mbox{unwinding} \end{align*} \]

Stack Overflow

Python will only allow a finite many recursive calls to be made. We say the recursion has overflowed when you exceed this limit.

Exceeding the stack limit does not necessarily mean we have a case of infinite recursion. Rather, our algorithms may legitimately require more stacks than what Python provides by default.

To increase the stack limit do, for instance

import sys
sys.setrecursionlimit(1500)  # default is 1000
fact(1000) 
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
fact(2000)
RecursionError: maximum recursion depth exceeded
fact(-1) 
RecursionError: maximum recursion depth exceeded
Note

The above information is mainly provided for completeness. In this course, we will not ask you to write any code that requires you to change the recursion limit. If you encounter a RecursionError while attempting any of the tasks in this course, it is almost certain that you have a bug in your code.

Non-Obvious Base Case

To handle non-obvious base cases consider an example that makes a single recursive call.

Ask what the base case must be in order for your example to work.

For example, consider \[ 2^k = 2 \cdot 2^{k-1} = 2 \times \cdots \times 2 \text{ $k$-many times} \]

What does zero-many times mean?

Notice we have \(2^1 = 2\) and \(2^1 = 2 \cdot 2^0\) and therefore \(2^0 = 1\).

Recursive functions defined over iterable types (e.g. lists, strings, and dictionaries) usually have as their base case the empty data structure:

Type Base Case
list []
str ''
dict {}

Exercises

Let us now solve problems using recursion.

Tip

  1. Ask yourself how you would solve the problem if you could solve the same problem on smaller examples.

  2. When in doubt, set the base cases to what they need to be in order for the singleton case to work. The singleton case is the second smallest one.

Exercise 1 Determine if a string is a palindrome. That is, a word that is equal to its reverse.

def is_palindrome(cs: str) -> bool:
    """
    Return True only when <cs> is a palindrome.
    
    >>> is_palindrome("dad")
    True
    >>> is_palindrome("racecar")
    True
    >>> is_palindrome("yo, banana boy!")
    False
    """

Note there is an obvious answer:

def is_palindrome(cs: str) -> bool:
    return cs == cs[::-1]

But suppose we want to avoid reversing the string. We could do the following which requires some index arithmetic.

def is_palindrome(cs: str) -> bool:
    for k in range(len(cs)//2):
        if cs[k] != cs[-k-1]:
            return False
    return True

But with recursion the arithmetic is more simple.

def is_palindrome(cs: str) -> bool:
    # base case
    if not cs:
        return True
    
    # recursive case
    return cs[0] == cs[-1] and is_palindrome(cs[1:-1])

Exercise 2 Recursively determine if a sentence is a palindrome, ignoring spacing, casing, and punctuation.

def sentence_palindrome(cs: str) -> bool:
    """
    >>> sentence_palindrome("Al lets Della call Ed `Stella'.")
    True
    >>> sentence_palindrome("Yo, banana boy!")
    True
    """
def sentence_palindrome(cs: str) -> bool:
    """
    Return True only when <cs> is a palindrome, ignoring spacing,
    casing, and punctuation.

    >>> sentence_palindrome("racecar")
    True
    >>> sentence_palindrome("Yo, banana boy!")
    True
    >>> sentence_palindrome("six-seven")
    False
    """

    if not cs:
        return True
    
    if not cs[0].isalpha():
        return sentence_palindrome(cs[1:])

    if not cs[-1].isalpha():
        return sentence_palindrome(cs[:-1])
    
    return cs[0].lower() == cs[-1].lower() and sentence_palindrome(cs[1:-1])

Exercise 3 Recursively flatten a list. That is, remove all internal brackets.

def flatten(xs: list) -> list:
    """
    Return the list obtained by removing all internal brackets
    from <xs>

    >>> flatten([1, [2], [[3,4]], [[5], [6, 7, 8], 9]])
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> flatten([[1, 2, 3], [4, [5, 6]]])
    [1, 2, 3, 4, 5, 6]
    """
def flatten(xs: list) -> list:
    """
    Return the list obtained by removing all internal brackets
    from <xs>

    >>> flatten([1, [2], [[3,4]], [[5], [6, 7, 8], 9]])
    [1, 2, 3, 4, 5, 6, 7, 8, 9]
    >>> flatten([[1, 2, 3], [4, [5, 6]]])
    [1, 2, 3, 4, 5, 6]
    """
    if not xs:
        return []
    
    if isinstance(xs[0], list):
        return flatten(xs[0]) + flatten(xs[1:])
    
    return [xs[0]] + flatten(xs[1:])

Exercise 4 Recursively check if a list of numbers is monotonically increasing.

def mono_inc(xs: list[int]) -> bool:
    """
    Return True when the members of <xs> are monotonically increasing.
    >>> mono_inc([1, 2, 3])
    True
    >>> mono_inc([1, 1, 1])
    False
    >>> mono_inc([3, 2, 1])
    False
    """
def mono_inc(xs: list[int]) -> bool:
    """
    Return True when the members of <xs> are monotonically increasing.
    >>> mono_inc([1, 2, 3])
    True
    >>> mono_inc([1, 1, 1])
    False
    >>> mono_inc([3, 2, 1])
    False
    """

    if len(xs) < 2:
        return True
    
    return xs[0] < xs[1] and mono_inc(xs[1:])

Exercise 5 Recursively sum the digits of a number. I.e., the sum of the digits 123 is 1+2+3=6.

def sum_digits(x: int) -> int:
    """
    Return the sum of the digits of <x>.

    >>> sum_digits(1234)
    10
    >>> sum_digits(7)
    7
    """
def sum_digits(x: int) -> int:
    """
    Return the sum of the digits of <x>.

    >>> sum_digits(1234)
    10
    >>> sum_digits(7)
    7
    """

    if x < 0:
        return sum_digits(-x)
    
    if not x:
        return 0
    
    return (x % 10) + sum_digits(x // 10)

Exercise 6 Recursively determine if xs: List[int] has a sublist that sums to some target.

def sublist_sum(xs: list[int], target: int) -> bool:
    """
    Returns True iff <xs> contains any sublist that sums to <target>.

    >>> sublist_sum([3, 5, 6, -3, 1, 2], 9)
    True
    >>> sublist_sum([3, 5, 6, -3, 1, 2], -1)
    True
    >>> sublist_sum([3, 5, 6, -3, 1, 2], 890)
    False
    >>> sublist_sum([1, 2], 0)
    True
    """
def sublist_sum(xs: list[int], target: int) -> bool:
    """
    Returns True iff <xs> contains any sublist that sums to <target>.

    >>> sublist_sum([3, 5, 6, -3, 1, 2], 9)
    True
    >>> sublist_sum([3, 5, 6, -3, 1, 2], -1)
    True
    >>> sublist_sum([3, 5, 6, -3, 1, 2], 890)
    False
    >>> sublist_sum([1, 2], 0)
    True
    """
    if not xs:
        return not target # True only for target = 0
    
    return sublist_sum(xs[1:], target - xs[0]) or sublist_sum(xs[1:], target)
Caution

The above creates a tree of recursive calls as every function invocation triggers two recursive calls. This can be a problem for large problems which can be solved by memoizing previous calls as we do in the Dynamic Programming section.

Exercise 7 Suppose you are standing on a grid at the origin and can only move along the x and y axis by positive increments.

Write a function which recursively determines how many distinct paths there are to an arbitrary position on the grid.

def num_paths(x_cord: int, y_cord: int) -> int:
    """
    Return the number of paths from (0, 0) to (x_cord, y_cord)
    when you can only move in positive directions along the x and
    y axis.

    >>> num_paths(1, 1)
    2
    >>> num_paths(1, 2)
    3
    """
    if (x_cord, y_cord) == (0, 0):
        return 1
    
    if x_cord < 0 or y_cord < 0:
        return 0
    
    return (num_paths(x_cord-1, y_cord) 
           +  num_paths(x_cord, y_cord-1))

Exercise 8 Implement a recursive function to solve the Towers of Hanoi problem.

def hanoi(num_disks: int, from_peg: int, 
          to_peg: int) -> list[tuple[int]]:
    """Move <num_disks> many disks labelled 1, 2, ..., num_disks
    from peg <from_peg> to <to_peg>. Pegs are numbered 0, 1, and 2.
    """
    if not num_disks:
        return []

    off_peg = 3-from_peg-to_peg
    
    return (hanoi(num_disks-1, from_peg, off_peg) 
            + [(num_disks, to_peg)] 
            + hanoi(num_disks-1, off_peg, to_peg))

Exercise 9 The string "abc" has eight substrings: "", "a", "b", "c", "ab", "ac", "bc", "abc".

Write a function that, given two strings, returns the longest common subsequence of those two strings.

def lcs(xs: str, ys: str) -> str:
    """
    >>> lcs("cbfbcdeb", "cbebcee")
    'cbbce'
    """
def lcs(xs: str, ys: str) -> str:
    """
    lcs("cbfbcdeb", "cbebcee")
    'cbbce'
    """
    if not xs or not ys:
        return ""

    if xs[0] == ys[0]:
        return xs[0] + lcs(xs[1:], ys[1:])
    
    return max(lcs(xs[1:], ys), lcs(xs, ys[1:]), key=len)

Dynamic Programming

One problem with recursion is its efficiency with branching recursions.

There is a strategy of caching previous results when doing recursion that is quite powerful when the branching recursion has many overlapping sub-problems. Caching is the process of saving previous computations using a dictionary so expensive computations only need to be performed once.

Fibonacci Sequence

The Fibonacci sequence is the canonical examples for dynamic programming because many computations need to be repeated while computing it. The \(n\)th number of this sequence is defined to be the sum of the previous two numbers in the sequence: \[ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34... \] and generally if \(F_n\) is the \(n\)th Fibonacci number then \[ F_n = F_{n-1} + F_{n-2} \] with \(F_0 = 0\) and \(F_1 = 1\).

Notice this means to obtain \(F_6\) we need to compute \(F_3\) three times because \[ \begin{align*} F_6 &= F_5 + F_4 \\ &= (F_4 + F_3) + (F_3 + F_2) \\ &= ((F_3 + F_2) + F_3) + (F_3 + F_2) \end{align*} \] and these repeated computations get worse for larger numbers. For instance, \(F_9\) is computed 1,346,269 times when computing \(F_{39}\).

def fib(n: int) -> int:
   """
   Return the nth Fibonacci number.
   """
   if n < 2:
       return n
   return fib(n-1) + fib(n-2)
import timeit # library for timing functions

# Number of seconds to compute the 39th fib number
timeit.timeit(lambda: fib(39), number=1)
15.87584277100001

If we store previous answers, then we can do the same computation much faster.

fib_cache = {0: 1, 1: 1}  # Base cases go here
def fib(n: int) -> int:
    global fib_cache

    # check if it is necessary to compute fib(n)
    if not n in fib_cache: 
        # remember this computation
        fib_cache[n] = fib(n-1) + fib(n-2)

    # otherwise just returned the cached outcome
    return fib_cache[n]
import timeit # library for timing functions

# Number of seconds to compute the 39th fib number
timeit.timeit(lambda: fib(39), number=1)
2.542700002550191e-05