https://www.xkcd.com/1739/
Previous: 13-AlgorithmsSoftware.html
Show self-recording screencast to start.
https://www.xkcd.com/1739/
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
https://en.wikipedia.org/wiki/Recursion
As with any constructive discussion, we start with definitions:
“To understand recursion, you must understand
recursion.”
What is base case above?
https://en.wikipedia.org/wiki/Recursive_acronym
* 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?”)
https://en.wikipedia.org/wiki/Natural_number
For example, 1, 2, 3, 4, …
Natural numbers are either:
n + 1, where n is a natural number, or
1
https://en.wikipedia.org/wiki/Exponentiation
For example, 28 = 256
Exponentiation:
bn = b * bn-1, or
b0 = 1
https://en.wikipedia.org/wiki/Factorial
For example,
5! = 5 × 4 × 3 × 2 × 1 = 120
Factorial:
n! = n * ((n - 1)!), or
0! = 1
14-Recursion/recursion_00_exp.py
++++++++++++++++++
Cahoot-14.1
https://mst.instructure.com/courses/58101/quizzes/56302
Ask: What is 2^-8 ^?
The recursive case looks just like your mathematical definition.
Recursive case:
bn = b * bn-1
Base case (termination):
b0 = 1 (or slightly faster, though less “correct”:
b1 = b)
Condition/test, which checks for the base:
if(n == 0):
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)??
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** ?**
What is b61** ?**
++++++++++++++++++
Cahoot-14.2
https://mst.instructure.com/courses/58101/quizzes/56303
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:
14-Recursion/recursion_01_order.py
https://en.wikipedia.org/wiki/Factorial
A slow complexity class, but computing factorial itself is not too slow
(these are different concepts).
Recursive case:
n! = n * ((n - 1)!)
Base case (termination):
0! = 1
Condition/test, which checks for the base:
if(n == 0):
Observe code
Example:
Factorial n! = n * ((n - 1)!)
0! = 1Observe code, and evaluate calling factorial of 3:
14-Recursion/recursion_02_factorial.py
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.
What happens when I run this??
14-Recursion/recursion_03_uh_o.py
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.https://en.wikipedia.org/wiki/Call_stack
Manages the stack of activation records.
pudb3 to see
the stack, for example factorial_rec.pudb3, which activation
records are most shallow, and which are most deep?Observe these while tracing:
Each record on the stack needs a return address (more on this in years to come).
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).
A single linear self-reference.
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:
Where the recursive call contains all computation, and mimics iteration.
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.
A function that calls a friend, that calls it back.
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:
14-Recursion/recursion_04_thats_odd.py
(a kind of multiple recursion)
https://en.wikipedia.org/wiki/Fibonacci_number
Fibonacci sequence definition:
Base case:
F0 = 0,
F1 = 1
Recursive case:
Fn = Fn-1 + Fn-2
Unpacked:
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.
**"To create recursion, you must create recursion."**
Compound interest guideline:
* Try not to duplicate work by solving the same instance of a problem in
separate recursive calls.
of recursion in code.
https://en.wikipedia.org/wiki/Palindrome
Observe code to show recursion stack:
14-Recursion/recursion_06_palindrome.py
Cool side-note: we use greedy boolean comparisons to quit early
(efficiently)!
++++++++++++++++++
Cahoot-14.3
https://mst.instructure.com/courses/58101/quizzes/56304
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:
14-Recursion/recursion_07_gcd.py
++++++++++++++++++
Cahoot-14.4
https://mst.instructure.com/courses/58101/quizzes/56305
**"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._HeinleinFor example, our first recursive Fibonacci implementation has a steeping computational complexity (is less efficient) than our iterative solution, no fibbing:
if n is zero, then fib(n) is: 0if n is one, then fib(n) is: 1
else, fib(n) is: fib(n - 1) + fib(n - 2)
* Observe recursive code:
14-Recursion/recursion_09_loop_to_recursion_fibonacci.py
* 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:
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.
Tail recursion is much like looping.
Often, but not always, developing tail recursive implementation, may
follow first writing an iterative solution.
++++++++++++++++++
Cahoot-14.5
https://mst.instructure.com/courses/58101/quizzes/56306
**"There is nothing so useless as doing efficiently that which should not be done at all."**
- https://en.wikipedia.org/wiki/Peter_Druckeris just a glorified loop.
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!
14-Recursion/recursion_10_loop_to_recursion_factorial.py
14-Recursion/recursion_11_loop_to_recursion_countdown.py
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.
https://en.wikipedia.org/wiki/Memoization
* 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
14-Recursion/recursion_12_memoization_dynamic_prog.py
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.
Often converting more inherently recursive algorithms to loops requires keeping a programmer-designed stack like would be done by the compiler in the first place.
See example for factorial (C++ examples from 1575 only for now; no stacks in CS1500)…
“Life can only be understood backwards;
but it must be lived forwards.”
- https://en.wikipedia.org/wiki/S%C3%B8ren_Kierkegaard
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:
14-Recursion/recursion_13_binary_search.py
https://en.wikipedia.org/wiki/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:
https://en.wikipedia.org/wiki/Metaheuristic
This is in-part because you can use the meta-heuristic so wrap
algorithms for a variety of problems, with slight modifications.
How do you fix your past mistakes??
For example, games such as: n-Queens, Knapsack problem, Sudoku, Maze, etc.
* 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.
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.
Else
undo the current move
If none of the moves work out, then
return FalseYou can use this meta-heuristic to solve a whole variety of problem types.
++++++++++++++++++
Cahoot-14.6
https://mst.instructure.com/courses/58101/quizzes/56307
We’ll go over Sudoku and maze-navigation now:
https://en.wikipedia.org/wiki/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.
Exercises:
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)?
recursive_sudoku()
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
Else
remove digit
If all digits were tried, and nothing worked, then
return FalseMy code for Sudoku:
14-Recursion/recursion_14_sudoku.py
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
Notes:
* 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!!
++++++++++++++++++
Cahoot-14.7
https://mst.instructure.com/courses/58101/quizzes/56308
