Present some examples of recursion in the real world:
Russian Dolls (dolls that fit inside one another, the smallest doll
is the base case)
Mirrors opposing each other (infinite recursion, no base case)
Put a set of instructions on the overhead or board:
1) If you receive one card, pass it back.
2) If you receive more than one card, pass it forward and take
one.
3) When a stack of cards is returned to you, insert your card
so that the stack is sorted.
Give one student the unsorted stack.
Show the given program for factorial:
define factorial(num):
if num == 1
return 1
else
return num * factorial(num
- 1)
Ask the students to trace the computation for factorial(5) in any way they'd like in a small group.
Ask the following questions:
1) What if you don't have a base case? What would happen?
2) What makes this computation recursive?
Ask students to come up with fibonacci algorithm in groups.
Note that recursion is a good technique for tree traversal (real world
use).
Contrast recursion with iterative methods, showing an iterative process
for calculating factorial.
1) Explain one example of a recursive process.
2) Have students come up with the recursive algorithm for other
examples in groups: factorial, detecting palindromes, fibonacci sequence,
pascal's triangle, binary search.
3) Connect vocabulary and concepts of recursion to the steps
of the recursive solution to examples.
4) Talk about the iteration versus tail recursion and their equivalence.
5) Ask why we would want to use recursion. Hard examples
for iteration, much easier to use recursion, breaking into groups.
Processes for which to use recursion: merge sort, printing singly-linked
lists, printing/traversing trees, parsing grammars.
Activity about factorial:
1) Select a non-volunteer (It's tough to get volunteers in a course
like 143).
2) Tell him/her that he/she knows 1!.
3) Select a new non-volunteer. Announce that he/she knows
2!.
4) How does the volunteer selected in step (3) know 2!?
Maybe ask 1! for his/her answer and multiply by 2.
5) Continue with 3!, 4! etc.
1) Show the factorial example and write the formula on the board.
2) Avoid the complete calculation.
3) Let students think about how one might calculate 5!.
4) Show actual recursive algorithm that calculates factorial.
5) Challenge the students to write the algorithm in code and
understand the process.
Show recursion step by step:
1) I.H. (Induction Hypothesis)
2) Base Case
3) Computation Tree
4) Stack
5) Higher Order
Each step is motivated by an example, for which they are given a minute or more to think and then tell them about the step.
For I.H. : the title suggest that.
For Base Cases: Factorial (They should be motivated to ask about
factorial(0)).
For Tree: Calculation of factorial step by step
For Stack: n^n
Higher Order: Fibonacci
Give students an example of tracing a factorial call.
fac(5)
5 * fac(4)
4 * fac(3)
3 * fac(2)
2 * fac(1)
1 * fac(0)
Then have students do a similar trace for calculating a fibonacci number.
1) Give students definition of fibonacci numbers.
2) Ask students to take on roles of different fibonacci numbers
(F0, F1, F2, F3, etc.)
3) Ask the 10th student who represents F9 what his/her value
is. This person then asks F8 and F7 what their values are which then
leads to more question-asking until we reach the base base. Once
a person gets a value, he/she reports it to the person who originally asked
for it.