1 14-Recursion

Previous: 13-AlgorithmsSoftware.html

Show self-recording screencast to start.


1.1 Screencasts

Lecture start/end points are noted below in the notes.
* Lecture 1: https://vimeo.com/521071999
* Lecture 2: https://vimeo.com/522062744
* [ ] Lecture 3: TODO split same material across 3
* Tip: If anyone want to speed up the lecture videos a little, inspect the page, go to the browser console, and paste this in:
document.querySelector('video').playbackRate = 1.2

1.2 Extra reading

1.3 Introduction


As with any constructive discussion, we start with definitions:
“To understand recursion, you must understand recursion.”

What is base case above?

1.3.1 Recursive humor

* GNU: GNU’s Not Unix
* YAML: YAML Ain’t Markup Language (initially “Yet Another Markup Language”)
* WINE: WINE Is Not an Emulator
* https://www.google.com/search?&q=recursion (notice the: “Did you mean recursion?”)

1.3.2 Familiar examples of recursion

For example, 1, 2, 3, 4, …

Natural numbers are either:
n + 1, where n is a natural number, or

For example, 28 = 256

bn = b * bn-1, or
b0 = 1

For example,
5! = 5 × 4 × 3 × 2 × 1 = 120

n! = n * ((n - 1)!), or
0! = 1

1.3.3 Recursive programming paradigm

1.3.4 The formal parts of a recursive algorithm

  1. Condition or test, often an if(), which tests for a
  2. base case (which often results in termination), which only executes once, after doing the
  3. recursive case repeatedly

1.4 Simple examples

1.4.1 Iterative exponentiation



1.4.2 What about negative exponents?

Ask: What is 2^-8 ^?

1.4.3 Recursive exponentiation

The recursive case looks just like your mathematical definition.

For example:
b4 =
b * b3 =
b * (b * b2) =
b * (b * (b * b1)) =
b * (b * (b * (b * b0)))

Real-world example: Exponentiation is used very frequently in big-cryptography. Imagine you have a web-server that makes 1 million connections a day. Some bitcoin server farms have power bills in the many millions per month!! How many dollars in power bills, or carbon dioxide production could you save with just an improvement from an improvement from a big theta of n to log2(n)??

1.4.4 Efficient exponentiation

To obtain bn, do recursively:
* if n is even, do bn_2 * bn_2  
* if n is odd, do b * bn_2 * bn_2
* with base case, b1 = b

Note: n//2 is integer (floor) division

What is b62** ?**

  1. b62 = (b31)2
  2. b31 = b(b15)2
  3. b15 = b(b7)2
  4. b7 = b(b3)2
  5. b3 = b(b1)2
  6. b1 = b

What is b61** ?**

  1. b61 = b(b30)2
  2. b30 = (b15)2
  3. b15 = b(b7)2
  4. b7 = b(b3)2
  5. b3 = b(b1)2
  6. b1 = b


1.4.5 Before or after: order of execution

Paying attention to order of code around recursive calls is important!!
* When a function calls itself, instructions placed before the recursive call are executed once per recursion, before the next call, “on the way down the stack”.
* Instructions placed after the recursive call are executed repeatedly after the maximum recursion has been reached, “on the way up the stack”.

Observe code:

1.4.6 Factorial

A slow complexity class, but computing factorial itself is not too slow (these are different concepts).

Observe code

Factorial n! = n * ((n - 1)!)

0! = 1

Observe code, and evaluate calling factorial of 3:

Since 3 is not 0, take second branch and calculate (n-1)!...
    Since 2 is not 0, take second branch and calculate (n-1)!...
        Since 1 is not 0, take second branch and calculate (n-1)!...
            Since 0 equals 0, take first branch and return 1.
        Return value, 1, is multiplied by n = 1, and return result.
    Return value, 1, is multiplied by n = 2, and return result
Return value, 2, is multiplied by n = 3, and the result, 6, becomes the
return value of the function call that started the whole process.

1.4.7 Uh o

What happens when I run this??
Actually run this… As you can see, recursion is the bomb!

**"Wherever you go, there you are"**
    - https://en.wikipedia.org/wiki/Jon_Kabat-Zinn
Recursive side note: one concrete definition of consciousness or awareness is meta-cognition, a form of self-referential thought.

1.5 The call stack

Manages the stack of activation records.

1.5.1 Activation record stack

Observe these while tracing:


Each record on the stack needs a return address (more on this in years to come).

1.5.2 Activation records

1.6 Types of recursion

Recursive programming variations: a partial overview

Single recursion:
* Contains a single self-reference
* e.g., list traversal, linear search, or computing the factorial function…
* Single recursion can often be replaced by an iterative computation, running in linear (n) time and requiring constant space.

Multiple recursion (binary included):
* Contains multiple self-references, e.g., tree traversal, depth-first search (coming up in future courses)…
* This may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
* Multiply recursive algorithms may seem more inherently recursive.
* Some of the slowest complexity-class functions known are multiply recursive; some were even designed to be slow!

Indirect (or mutual) recursion:
* Occurs when a function is called not by itself, but by another function that it called (either directly or indirectly).
* Chains of 2, 3, …, n functions are possible.

Generative recursion:
* acts on outputs it generated (e.g., a mutated mutable List)

Structural recursion:
* acts on progressive newly generated sets of input data (e.g., a copied immutable string).

1.6.1 Linear recursion

A single linear self-reference. Example: Factorial version 1

As above, this is another way to define factorial:
* The first line is the base case.
* The second line is the recursive call.
* Notice that the recursive call to f() does NOT contain all statements.
* Specifically n * resides outside the call.

Example call-tree for factorial definition:

1.6.2 Tail recursion

Where the recursive call contains all computation, and mimics iteration. Example: Factorial version 2

Factorial definition with tail-call design:
* The first line is the base case.
* The second line is the recursive case.
* Notice that the recursive call to f() contains all statements, with none outside f().
* This mimics an iterative construction in some way.

Example call-tree for tail-call factorial definition:
This is potentially more efficient.

1.6.3 Mutual recursion

A function that calls a friend, that calls it back. Example: Even or odd?

A pair of functions that each return a Boolean:


* This is an inefficient way to check for even or odd numbers…
* To expand on that side note, check out the code:

1.6.4 Binary recursion

(a kind of multiple recursion) Example: Fibonacci sequence

Fibonacci sequence definition:

Base case:
F0 = 0,
F1 = 1

Recursive case:
Fn = Fn-1 + Fn-2

1, 1, 2, 3, 5, 8, 13, …


Functional set-notation definition:

What the call-tree could look like:
Do you see any problems here?

Wait on code trace for this function until efficiency section below.

1.7 Recursive design: Implementation

**"To create recursion, you must create recursion."**

1.7.1 How to design a recursive algorithm

  1. First design and write the base case(s) and the conditions to check it!
  2. Think about solving the problem by combining the results of one or more smaller, but similar, sub-problems.
  3. Make real progress
  4. Check progressively larger inputs to inductively validate that there is no infinite recursion
  5. Do not worry about how the recursive call solves the sub-problem.

Compound interest guideline:
* Try not to duplicate work by solving the same instance of a problem in separate recursive calls.

1.7.2 Examples

of recursion in code. Simple word reversal Palindrome checking function


Observe code to show recursion stack:
Cool side-note: we use greedy boolean comparisons to quit early (efficiently)!

https://mst.instructure.com/courses/58101/quizzes/56304 Greatest common divisor (GCD)

Euclid’s algorithm efficiently computes the greatest common divisor (GCD) of two numbers (AB and CD below), the largest number that divides both without leaving a remainder (CF).

Proceeding left to right:
* Check out the code, loop then recursive:

https://mst.instructure.com/courses/58101/quizzes/56305 Sum

1.8 +++++++++++ Lecture 2 starts here

**"Progress isn't made by early risers.**
**It's made by lazy men trying to find easier ways to do something."**
     - https://en.wikipedia.org/wiki/Robert_A._Heinlein

1.9 Efficiency

1.9.1 Problem: re-computing values

1.9.2 Example: Fibonacci and efficiency

* Observe recursive code:
* Step f(3) all the way deep.
* When you step a multiply recursive line, which gets called first, left or right?
* This algorithm produces something like a depth-first enumeration of the above tree.
* While it is nice that the python code looks like our mathematical definition, it is inefficient!
* How long does fib_rec(35) take?
* How many iterations?

* How long does fib_loop(35) take?
* How many iterations?
* There are a number of solutions to this problem of efficiency:

1.9.3 Solution 1: Use a loop

If you can easily find a looping algorithm
(e.g., Fibonacci with a loop below)
* Observe iterative code.
* The larger the n, the worse the recursive solution becomes, in comparison to the iterative.
* This is what it means to have a worse complexity.
* Remember, recursion is just another way to loop.
* Successfully designing an iterative algorithm to replace a recursive one is not always easily possible.

1.9.4 Solution 2: Tail recursion calls

Tail recursion is much like looping.
Often, but not always, developing tail recursive implementation, may follow first writing an iterative solution.


**"There is nothing so useless as doing efficiently that which should not be done at all."**
    - https://en.wikipedia.org/wiki/Peter_Drucker Tail recursion

is just a glorified loop. Iterative conversion

converts an iterative loop into a tail recursion.

Systematic steps:
1. First identify those variables that exist outside the loop, but are changing in the loop body; these variable will become formal parameters in the recursive function.
2. Then build a function that has these “outside” variables as formal parameters, with default initial values.
3. The original loop test becomes an if() test in the body of the new function.
4. The if-true block becomes the needed statements within the loop and the recursive call.
5. Arguments to the recursive call encode the updates to the loop variables.
6. else block becomes either the return of the value the loop attempted to calculate (if any), or just a return.
7. Conversion results in tail recursion.

Code examples:
* See multiple examples in code (fib, fact, countdown), match them to the above steps in detail.
* This is really cool; it is a systematic way to convert any loop to recursion, by just following those above steps in rote form!



Note: A future lab will involve solving several problems iteratively and recursively. For each problem, you will implement one iterative solution and one recursive solution. To program the recursive solution, you could either:
1. Implement a natural recursive solution by inventing one creatively, or
2. Implement an iterative solution, and then perform the above systematic conversion to use tail-call recursion from your iterative solution. Language choice

1.9.5 Solution 3: Memoization / caching

* Memoization and caches (stores) the values which have already been computed, rather than re-compute them.
* It speeds up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.
* See code for Fibonacci

1.10 Convert recursion to a loop?

Conversion of recursive functions to loops is:
* less systematic than converting a loop to tail recursive,
* requires more creativity, and
* isn’t always easy for a human,
* though converting an already tail recursive algorithm is more straightforward.

1.10.1 Implementing recursion with a stack

1.11 Realistic examples

How might we implement this form of search recursively?
* What is the base case?
* What is the incrementally smaller case?
* What is the condition?

See code:

1.11.2 Example 2: Recursive backtracking

Backtracking finds all (or some) solutions to some computational problems, notably constraint satisfaction problems, by incrementally building candidates to the solutions, and abandoning a candidate (“backtracking”) as soon as it determines that the candidate cannot possibly be completed as a valid solution.

It is actually what is known as a general meta-heuristic, rather than an algorithm:
This is in-part because you can use the meta-heuristic so wrap algorithms for a variety of problems, with slight modifications. Problem: Hindsight

How do you fix your past mistakes??

For example, games such as: n-Queens, Knapsack problem, Sudoku, Maze, etc. Solution: Backtracking

* Backtracking
* is a general meta-heuristic that incrementally builds candidate solutions by a sequence of candidate extension steps, one at a time, and abandons each partial candidate, c, (by backtracking) as soon as it determines that c cannot possibly be extended to a valid solution.
* can be completed in various ways, to give all the possible solutions to the given problem.
* can be implemented with a form of recursion, or stacks to mimic recursion.
* refers to the following procedure: If at some step it becomes clear that the current path that you are on can’t lead to a solution, you go back to the previous step (backtrack) and choose a different path. General meta-heuristic
Pick a starting point.
recursive_function(starting point)
    If you are done (base case), then
        return True
    For each move from the starting point,
        If the selected move is valid,
            select that move,
            and make recursive call to rest of problem.
            If the above recursive call returns True, then
                return True.
                undo the current move
    If none of the moves work out, then
        return False

You can use this meta-heuristic to solve a whole variety of problem types.

https://mst.instructure.com/courses/58101/quizzes/56307 Examples implementing backtracking

We’ll go over Sudoku and maze-navigation now: Sudoku


Starting board (not initial configurations all are solvable, but this one is):

Finish (win):
* Board is 81 cells, in a 9 by 9 grid
* with 9 zones,
* each zone being the intersection of the first, middle, or last 3 rows, and the first, middle, or last 3 columns.
* Each cell may contain a number from one to nine;
* each number can only occur once in each zone, row, and column of the grid.
* At the beginning of the game, some cells begin with numbers in them, and the goal is to fill in the remaining cells.


What would be your human Sudoku strategies?
How might we solve this non-recursively (iteratively)?
* Where would you start?
* What might you loop across?
* How would you end?
* What sub-functions might you want?
How about recursively?
* What is the base case?
* What is an incrementally smaller version?
* What is the condition/check?
* Which functions do we need (do they overlap from the iterative version we drafted above)?

    Find row, col of an unassigned cell, an open move
    If there are no free cells, a win, then
        return True
    For digits from 1 to 9
        If no conflict for digit at (row, col), then
            assign digit to (row, col)
            recursively try to fill rest of grid
            If recursion successful, then
                return True
                remove digit
    If all digits were tried, and nothing worked, then
        return False

My code for Sudoku:
Note: I originally wrote this for C++, and then converted it to python, so this python code has a bit of a C-style to it.

As we trace this, pay attention to:
* diving deeper by stepping,
* the first time backtracking happens,
* look-ahead versus look-behind,
* whether a function call is responsible for reversing it’s own move, or the move of another function call,
* the final termination condition

* This code is a BIG hint for a future assignment.
* Your maze’s code macro-structure can be essentially identical to the Sudoku code above.
* If it diverges, you should fix it to match what I’ve given here!!

https://mst.instructure.com/courses/58101/quizzes/56308 Mazes

Next: 15-ClassesInheritance.html