Recursion

Recursion

There is still one type of proof we need to cover… but first we’re going to take a little bit of a detour.

It is helpful to understand recursion before we move on to the next kind of proof!

What is recursion?

Recursion is the idea of solving a problem by breaking it into smaller problems.

Example - Factorials:

  • A familiar function we know is \(n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1\)
  • We can rewrite this as \(n! = n\cdot (n-1)!\).
  • This is a recursive definition because we are computing \(n!\) by first computing \((n-1)!\).

Recursion in Coding

Here is an example of what recursion would look like in a programming language like Python.

Say we want to write a program that returns \(n!\).

Def factorial:
    input: natural number n
    if n == 1: #base case
        return 1
    else: #recursive rule
        return n * factorial(n-1) 
    

Why do we use recursion?

  • Breaking a problem into smaller pieces can make it easier to solve.
  • Breaking a problem into smaller pieces can also make it easier to reason about, making it easier to prove properties about it!
  • Many programming languages heavily rely on recursive definitions (haskell, racket, scheme, etc.)
  • Other programming languages support it by letting a function call itself.

Defining recursion

We just gave an example of a function that is defined recursively.

You can also recursively define sets, relations, tuples, lists, sequences, etc…

There are two main parts of any recursive definition:

  1. The base case: the initial element/value of what you’re trying to define
  2. The recursive rule: tells you how to generate the next element/value given previous ones.

Example: Factorials

  1. The base case: \(1! = 1\)
  2. The recursive rule: \(n! = n \cdot (n-1)!\)

The Fibonacci numbers

  • The Fibonacci numbers are a very famous sequence of numbers that are defined via a recursive function.
  1. The base case: \(F(0) = 0, F(1) = 1\)
  2. Recursive rule: For \(n > 1\), \(F(n) = F(n-1) + F(n-2)\).

Other Example - Powersets:

  • We can define powersets recursively:
  • \(\mathscr{P}(X + \{c\} ) = \mathscr{P}(X) \cup (\mathscr{P}(X) + \{c\})\)
  • E.g. \(\mathscr{P}(\{1,2,3\}) = \mathscr{P}(\{1,2\} + \{3\}) = \mathscr{P}(\{1,2\}) \cup (\mathscr{P}(\{1,2\}) + \{3\})\)
  • This is essentially saying we can build a powerset by unioning two smaller sets. We are building something by combining two smaller things. That’s what makes this definition recursive.

Definition

  1. The base case: \(\mathscr{P}(\{ \}) = \{\}\)
  2. The recursive rule: \(\mathscr{P}(X + \{c\}) = \mathscr{P}(X) \cup (\mathscr{P}(X) + \{c\})\)

Defining Lists Recursively

  • We are going to give an example of how we can define a list and some functions on a list recursively
  • Say all elements of our list are in set \(A\)
  • The set of all possible lists \(L\) can be defined as \(L = \bigcup_{k\geq0}A^k\) (Aka all possible permutations of length \(k \geq 0\) of the elements in \(A\).)
  • We can also define this recursively.
  1. Base case: Empty list \(\langle ~ \rangle\)
  2. Recursive rule: For any element \(a \in A\) and all lists \(l \in L\), \(cons(a,l)\) is a list in \(L\).
  • Basically, \(cons(a,l)\) takes \(a\) and attaches it to list \(l\)
  • You can think of “\(cons\)” as short for “constructor”.

Defining Lists Recursively

  1. Base case: Empty list \(\langle ~ \rangle\)

  2. Recursive rule: For any element \(a \in A\) and all lists \(l \in L\), \(cons(a,l)\) is a list in \(L\).

  • Basically, \(cons(a,l)\) takes \(a\) and attaches it to list \(l\)

Examples

  • \(\langle b \rangle = cons(b, \langle ~ \rangle)\)
  • \(\langle a, b \rangle = cons(a, cons(b, \langle ~ \rangle))\)
  • \(\langle a, b, c \rangle = cons(a, cons(b, cons(c, \langle ~ \rangle)))\)

Useful Partial Functions

  • \(head(cons( a,l )) = a\)
  • \(tail(cons( a,l )) = l\)
  • Note that \(head\) returns an element and \(tail\) returns a list!

Examples

  • \(\langle a, b, c \rangle = cons(a, cons(b, cons(c, \langle ~ \rangle)))\)
  • \(head(cons(a, cons(b, cons(c, \langle ~ \rangle)))) = a\)
  • \(tail(cons(a, cons(b, cons(c, \langle ~ \rangle)))) = cons(b, cons(c, \langle ~ \rangle)) = \langle b, c \rangle\)

Strings and Languages

  • Strings and Languages are likely going to come up later in your computer science education, so it’s good to be familiar with these definitions!
  • A string is a list containing characters from a given alphabet \(\Sigma\)
  • The set of all possible strings that can be made from an alphabet is \(\Sigma^*\)
  • A language is a set of strings \(L \subseteq \Sigma^*\)