Recursion

Introduction to Software Engineering (CSSE 1001)

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)\wedge (P(n)⟹P(\succ (n))))⟹\mathrm{\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 the successor (i.e. the number after) of $n$,

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

Example: 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

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

Proof of Tiling

Base Case ($n=0$). 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.

Proof of Tiling

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. That is,

if base_case:
    return constant

Recursive Step

A line where the function calls itself on “smaller” input.

The canonical example for a recursive function is the factorial.

Factorial

Let $n\in \mathbb{N}$ then the factorial of $n$, denoted $n!$ is given by $$n!=\{\begin{array}{ll}1& \text{when }n=0\\ n\times (n-1)!& \text{otherwise}\end{array}$$ 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{array}{r}\text{factorial}(4)\\ & \leftarrow 4\times \text{factorial}(3)\\ & \leftarrow 4\times (3\times \text{factorial}(2))\\ & \leftarrow 4\times (3\times (2\times \text{factorial}(1)))\\ & \leftarrow 4\times (3\times (2\times (1\times \text{factorial}(0))))\end{array}$$ 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{array}{rl}\text{factorial}(4)& \text{winding}\\ & ⋮& ⋮\\ & \leftarrow 4\times (3\times (2\times (1\times \text{factorial}(0))))& \text{winding}\\ & \leftarrow 4\times (3\times (2\times (1\times 1)))& \text{unwinding}\\ & \leftarrow 4\times (3\times (2\times 1))& ⋮\\ & \leftarrow 4\times (3\times 2)& ⋮\\ & \leftarrow 4\times 6& ⋮\\ & \leftarrow 24& \text{unwinding}\end{array}$$

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.

Note

Exceeding the stack limit does not necessarily mean we are bottoming out. 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

Base Case

fact(998) 
40279005012722099453824067459760158730668154575647110364744735778772623863726628
fact(999)  
RecursionError: maximum recursion depth exceeded

import sys
sys.setrecursionlimit(1001)

fact(999) 
40238726007709377354370243392300398571937486421071463254379991042993851239862902

fact(-1) 
RecursionError: maximum recursion depth exceeded  # Bottoming out

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 2k\text{-many times}$$

What does 0-many times mean?

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

Base Case

Recursive functions defined over lists and strings usually have as their base case the empty list and the empty string.

Type	Base Case
list	[]
str	'' (empty string)

Let us now solve problems using recursion.

Advice

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

Advice

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.

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

Obvious answer.

def is_palindrome(cs: str) -> True:
    return cs == cs[::-1]
is_palindrome("racecar")
True
is_palindrome("deified")
True
is_palindrome("squid")
False

Suppose we want to avoid reversing the list.

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

With recursion.

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

Determine if a sentence is a palindrome, ignoring spacing, casing, and punctuation.

def sentence_palindrome(cs: str) -> bool:
    pass

xs = "Al lets Della call Ed `Stella'."
sentence_palindrome(xs)
True
ys = "Yo, banana boy!"
sentence_palindrome(xs)
True

Flatten a list. That is, remove all internal brackets.

[1, [2], [[3,4]], [[5], [6,7,8], 9]]
[1, 2, 3, 4, 5, 6, 7, 8, 9]

def flatten(xs: list) -> list[int]:
    if not xs:
        return xs  # base case
    
    if type(xs[0]) is int:
        return xs[0:1] + flatten(xs[1:])  # recursion
    
    return flatten(xs[0]) + flatten(xs[1:])  # recursion

Check if a list of numbers is monotonically increasing.

def increasing(xs: List[int]) -> bool:
    if len(xs) <= 1:    # base case
        return True
    return xs[0] < xs[1] and increasing(xs[1:])    # recursion

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

def sum_of_digts(n: int) -> int:
    if not n:
        return 0
    
    return (n % 10) + sum_of_digts(n // 10)

Determine if xs: List[int] has a sublist that sums to some target.

xs = [3, 5, 6, -3, 1, 2]
sublist_sum(xs, 9)
True  # [3, 5, 1] 
sublist_sum(xs, -1)
True  # [-3, 2] 

def sublist_sum(xs: List[int], target: int) -> bool:
    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)

Note The above creates a tree of recursive calls as every function invocation triggers two recursive calls.

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

How many distinct paths are there to an arbitrary position on the grid?

def num_paths(x_cord: int, y_cord: int) -> int:
    """
    How many paths from (0, 0) to x_cord, y_cord when you can
    only move in positive direction.
    """
    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)

Return a solution to 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))

Write a function that tiles (with distinct numbered tiles) a $2^n\times 2^n$ board so that only one square is left uncovered.

Zero denotes the untiled square.

def tile(n: int) -> List

[List[int]]:
   pass
tile(2)
[[0, 2, 3, 3],
 [2, 2, 1, 3],
 [4, 1, 1, 5],
 [4, 4, 5, 5]]

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 subproblems.

def fib(n: int) -> int:
   """ Return the nth Fibonacci number."""
   if n < 2:
       return 1
   return fib(n-1) + fib(n-2)

With caching is much faster…

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

    if n in fib_cache:
        return fib_cache[n]

    fib_cache[n] = fib(n-1) + fib(n-2)
    return fib_cache[n]

Next Week

1. Last lecture!
2. Functional programming, and
3. Complexity.