BACK

Recursion

NEXT

Code from Sedgewick's Chapter 5

PowerPoint presentations:     Koffman&Wolfgang, Ch. 7       Locally maintained slide set.

Recursive code slides for projection:    Binary Search     Selection Sort     Insertion Sort     Merge Sort

Full Java implementation containing the code:  BinSrchRecursive.java [txt]    Result of a run

Stack overflow example:    Stupid.java    [txt]    Output on run attempt      Error log on run attempted

Towers of Hanoi example:   Code slide
HanoiBAS.exe   QuickBasic executable (Microsoft operating system required) animating the Towers of Hanoi
HanoiBAS.bas   QuickBasic source code, if you want to examine it  [txt]

TraceFib.java      Program to trace calls in computing Fibonacci numbers  [txt]    [exe]
TreeFib.java        TraceFib above, amplified to provide a "tree-view" of the result    [txt]   [exe]

IntPow.java [txt] A bad and a good implementation of Math.pow(x,exp)   IntPow.exe   JSmooth .exe wrapper

Paper on good and bad recurrences/recursion:  Binomial Coefficient Recursion:  The Good, and The Bad and Ugly


Enrichment Material (not subject to examination)

AdditiveSquares.java  [txt]  Based on addition and subtraction only, compute n2 recursively using only 3n addition/subtraction operations

Efficient alternative formulation for recursive Fibonacci numbers.  A "dynamic programming" example using "memoization."

Hanoi-NR.cpp  NON-recursive implementation in Borland C++ — uses screen positioning specific to Borland C++
Hanoi-NR.exe  Executable from Borland C++
Hanoi_NR.bas  Implementation in QuickBasic / QBasic
Hanoi_NR.exe  Executable from QuickBasic

Hanoi_mn.java  Towers of Hanoi as a self-recursive main method  [txt]

Famous example of a really nasty recursive function:
http://en.wikipedia.org/wiki/Ackermann_function

Java implementation with driver

http://planetmath.org/encyclopedia/AckermannFunction.html

Conway notationKnuth notation.