Programming languages support recursion. In a recursive program a function calls itself to solve smaller subproblems. When you write a recursive program you are applying abstraction: ignoring how smaller subproblems are solved in order to solve the big problem.
We present a number of recursive algorithms. Some relate to problems already covered in other blog entries (primarily on loops and functions). For the first two examples, Towers of Hanoi and Tiling with Trominos, we describe recursion solutions in a visual way, but provide no programs. Describing recursive algorithms without programs is often not as effective and we provide programs for most other examples.
- Example 1: Towers of Hanoi
- Example 2: Tiling with trominos
- Example 3: Binary Search
- Example 4: Reversing a string
- Example 5: Computing a Fibonacci number
- Example 6: Finding the greatest common divisor of two integers (GCD)
- Example 7: Koch Snowflake and Other Fractals
- Example 8: Sorting
See http://openbookproject.net/thinkcs/python/english3e/recursion.html for additional recursive Python programs with a good discussion on recursion.
