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

- It is induction on the

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

- Problem: find an element in a
- 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.