Recursive Definitions

It is sometimes difficult to give an explicit formula for a function/sequence.
- It can sometimes be easier to give a definition that says how the next value in the sequence is different from the last.
e.g. the logistic map which is about population growth rates. The population next year doesn't have an obvious formula, but depends on the population this year.
- Let \(x\) be the fraction of maximum possible population (0 to 1) and \(r\) be the rate of reproduction.
- Then if this year's population is \(a_n\), we can say next year's population is \(a_{n+1} = ra_n(1-a_n)\).
- Can you come up with a formula for \(a_n\)? Me neither.
- A moderately realistic model of simple population.
- … with some surprising behaviour. Try iterating for \(r=3.4\) and \(r=3.7\).
That sequence was defined recursively because the definition depended on a previous value of the sequence.
The most famous recursively-defined sequence is the Fibonacci sequence which are defined by: \[f_0=0\,,\\f_1=1\,,\\f_n=f_{n-1}+f_{n-2}\,.\]
- The first few values of the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89.
- The Fibonacci numbers also have a lot of surprising properties, and come up in unexpected places.
- Can you come up with a formula for \(f_n\)? Me neither.
- … but someone else did: \[f_n = \frac{\phi^n-(1-\phi)^n}{\sqrt{5}} \text{ where }\phi=\frac{1+\sqrt{5}}{2}\,.\]
- One of those definitions is much more informative than the other.
- Aside: the closed-form equation isn't even much use for calculating \(f_n\). It relies on floating point mathematics and rounding error means you'll get incorrect answers for large \(n\).
It may be simpler to think of factorial as being defined recursively: \(0!=1\) and \(n!=n\cdot(n-1)!\).

Recursive Definitions and Induction

Recursive definitions obviously lend themselves nicely to proof by induction.
Example: In the logistic equation, if we have \(0\lt a_0\lt 1\) and \(0\lt r\lt 4\) then for all \(n\), we have \(0\lt a_n\lt 1\). In other words: the population stays between 0 and 1 forever.

Proof: For the base case, take \(n=0\). There we have the conclusion as a premise.

For \(n\gt 0\), assume for induction that \(0\lt a_{n-1}\lt 1\) and consider \(a_{n} = ra_{n-1}(1-a_{n-1})\).

Because of calculus, the function \(a(1-a)\) has a maximum value of \(1/4\) at \(a=1/2\) and is greater than zero for all \(0\lt a \lt 1\). Then, since \(0\lt a_{n-1}\lt 1\), we have \[ 0 \lt a_{n-1}(1-a_{n-1}) \lt 1/4 \\ 0 \lt ra_{n-1}(1-a_{n-1}) \lt 1 \\ 0 \lt a_n \lt 1\,.\quad ∎ \]
If we define non-numeric things recursively, they can also lend themselves to induction proofs.
For example, we can define a set of palindromes (strings that are the same when reversed) as the set \(P\) where for any character \(c\), \[ “c”\in p\\ s\in P \rightarrow “c”+s+“c” \in P\,. \]
Example: Elements in the set \(P\) have an odd length.

Proof: For the first rule, the string \(“c”\) has length 1 and 1 is odd.

Longer strings in the set must come from the second rule. Then for induction, assume that the string \(s\) has length \(n\) where \(n\) is odd. Then \(“c”+s+“c”\) has length \(n+2\) which is odd.∎
This is called structural induction.
- It is induction on the structure of the object, not an integer.
- If you really want, you could think of that proof as induction on elements of \(P\) with \(n\) rules applied. Then it would look more like our other induction proofs.

Recursive Algorithms

The basic idea behind induction is that we can use a proof values \(<n\) to establish the truth for \(n\).
We can use this same general idea to create an algorithm.
- Can we solve the problem for smaller inputs, and then use that to solve for the input we have?
- These will be called recursive algorithms.
Here is an algorithm that we have seen before (with a few less details):
```
procedure selection_sort(list)
    for i from 0 to length(list)-1
        find the smallest element in list[i…]
        swap it into position i
```
- What does it do?
- Get the smallest element into the correct position, and then continue doing the same thing on the rest of the list.
Hmmm… “the same thing on the rest of the list.”
Here is an algorithm that we have seen before, expressed recursively:
```
procedure selection_sort(list)
    if length(list) = 0
        return
    else
        find the smallest element in the list
        swap it into position 0
        selection_sort(list[1…])
```
- This procedure calls itself (with different arguments). That's okay. Every programming language you have ever touched can do that.
- What it's basically doing is getting element 0 into place, and then magically (recursively) sorting the rest of the list.
Does it work? Rough proof by structural induction:
- Our base case is lists of length 0. Nothing is required to sort an empty list correctly, and it does nothing.
- For longer lists, it definitely gets the first element in the right place. If the algorithm correctly sorts lists of length \(n-1\), then the whole list is sorted at the end.
Here is an algorithm that is harder to express without recursion:
- Problem: find an element in a sorted list.
- We will implement it as “find an element in a sorted list from position start to end, inclusive.”
- So, our initial call should be binary_search(list, 0, length(list)-1, value).
- Why we're doing that should become obvious.
```
procedure binary_search(list, start, end, value)
    if start > end
        return -1
    else
        middle = ⌊(start+end)/2⌋
        if list[middle] = value
            return middle
        elseif list[middle] < value:
            return binary_search(list, middle+1, end, value)
        elseif list[middle] > value:
            return binary_search(list, start, middle-1, value)
```
- This relies on the observation: since the list is sorted, if we look at list[middle] and find something too small, the thing we're looking for is definitely nowhere in list[start…middle]. We can ignore that part of the list and only search list[middle+1…end].
- … and similarly if we find something too big.
We could have expressed binary search using loops instead of recursion (iteratively).
- The text does in section 3.1.
- It's uglier to read; less obvious that it works.
Both examples could be expressed recursively and iteratively.
- Is that always possible? Can you always transform an algorithm iterative ↔ recursive?
- Yes, but it's not always easy.
- There are definitely some algorithms that are easier to express recursively.
- Most would say that there are some that are better expressed iteratively too.
What is the running time of binary search?
- Obvious: each recursive step uses \(O(1)\) time.
- How many times does it recurse (in the worst case)?
- Starts with \(n\) elements in the list, then \(n/2\), then \(n/4\), …, then 2, and 1.
- How many times can you divide \(n\) in half before you get to one?
- \(\Theta(\log n)\).
- That's a big improvement over our earlier \(\Theta( n)\) search, if the list is sorted.
Back to recursion…

Euclid's algorithm is a lot easier to express recursively too:

procedure gcd(a, b)
    if a = 0
        return b
    else
        return gcd(b mod a, a)

Note that in each case, our algorithm is of the form “if we're done return the answer else do the recursive thing.”
- The fundamental reason: if we don't stop the recursion somewhere, the function never stops.
- An infinite recursion. Same as an infinite loop for iterative algorithms.
- The non-recursive case where we just return is called the base case.
- The one where we do recursion is called the recursive case(s).

Here's an algorithm you'd probably struggle to write iteratively: mergesort.

The idea: take the list and break it in half. Sort both halves. Combine (merge) the two halves so everything is in order.

procedure mergesort(list, start, end)
    if start ≥ end
        return
    else
        middle = ⌊(start+end)/2⌋
        mergesort(list, start, middle)
        mergesort(list, middle+1, end)
        merge(list, start, middle, end)

procedure merge(list, start, middle, end):
    i = 0
    until you're out of elements     # obviously ignoring some details here
        if list[start] ≤ list[middle+1]
            newlist[i] = list[start]
            start += 1
        else:
            newlist[i] = list[middle+1]
            middle += 1
        i += 1
    copy newlist to list

In mergesort, we made two separate recursive calls, on the left and right halves of the list.
- Will also work. It's what makes writing this iteratively hard.
What's the running time?
- Running time of the merge is \(\Theta(n)\).
- Total running time is \(\Theta(n\log n)\).
- Best, worst, and average cases are the same.
- It turns out: \(O(n\log n)\) is an upper bound for any comparison-based sorting algorithm.
What are the memory requirements?
- The merge requires \(\Theta(n)\) extra storage.
Honest opinion: being able to use recursion is one of the things that separates really good programmers from everybody else.
- Not only answering questions “write a recursive function that…”, but being able to look at a new problem and think “doing this recursively would be easier.”
- Something else that separates them: an intuitive understanding of big-O bounds, and when they should go looking for a better algorithm.
The kind of thinking that goes into a proof by induction is very similar to writing recursive algorithms.
- Both need a base case: where is the easy place where you can stop?
- Both need the step to go from smaller to bigger solutions/conclusions.
- If you wanted to prove a recursive algorithm was correct, it's fundamentally going to be a proof by induction.