Recursion Examples

Order of Recursive Calls

Goal : print out a cascading tree of a positive integer n

Ideas :

-   If n is a single digit, just print it out !

-   Otherwise, let cascade ( n // 10 ) take care of the middle and print(n) around it

The cascade function

: Each cascade frams is from a different call to cascade

: Until the Return value appears, that call has not completed

: Any statement can appear before or after the recursive call

Two Implementations of cascade

-   If two implementations are equally clear, then shorter is usually better

-   In this case, the longer implementation might be more clear

-   When learning to write recursive functions, put the base case/s first

Fibonacci

Fibonacci Sequence

Goal : Return the nth Fibonacci number

Ideas :

-   The first two Fibonacci numbers are known; if we ask for other -th or 1st Fibonacci number, we k

-   

Fibonacci Call Tree

fib(n) : a tree-recursive process

Broken Fibonacci

Counting Partitions

Goal : Count the number of ways to give out n ( > 0 ) pieces of chocolate if nobody can have more than m ( > 0 ) pieces.

Ideas :

-   Find simpler instances of the problem

-   Explore two possibilities ( use a 4 / don't use a 4 )

-   Solve two simpler problems :

count_part ( 2, 4 ) / count_part ( 6, 3 )

-   Sum up the results of these smaller problems

How do we know we're done ?

-   If n is negative, then we cannot get to a valid partition

-   If n is 0, then we have arrived at a valid partition

-   If the largest piece we can use is 0, then we cannot get to a valid partition