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