CSC 143/Chapter 12

Chapter 12: Recursion

Sections:

12.1 Thinking recursively

12.2 A better example of recursion

12.3 Recursive functions and data

12.4 Recursive graphics

12.5 Recursive backtracking

12.6 Case study: Prefix evaluator

Section 12.1: Thinking Recursively

Material

A non-programming example

An iterative solution converted to recursion

Structure of recursive solutions

Section 12.2: Better Example of Recursion

Material

Mechanics of recursion

Section 12.3: Recursive Functions and Data

Material

Integer exponentiation

Greatest common divisor

Directory crawler

Helper methods

Section 12.5: Recursive Backtracking

Material

A simple example: traveling north/east

8 Queens Puzzle

Solving Sudoku puzzles

Section 12.6: Case Study: Prefix Evaluator

Material

Infix, prefix, and postfix notation

Evaluating prefix expressions

Complete program

Chapter 12 Summary

Deliverables

Recursive thinking, breaking down an "obviously" recursive algorithm.

Chapter 12 Goodies

Quotes

In 2002, Noam Chomsky co-wrote a paper stating that recursion is the "only uniquely human component of the faculty of language."

Buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo.

NY animals ((that) NY animals bully) bully NY animals ((that) NY animals bully)

A child couldn't sleep, so her mother told a story about a little frog,
  who couldn't sleep, so the frog's mother told a story about a little bear,
     who couldn't sleep, so bear's mother told a story about a little weasel
       ...who fell asleep.
     ...and the little bear fell asleep;
  ...and the little frog fell asleep;
...and the child fell asleep.

The rule of thumb for recursion is, "Use recursion, if and only if on each iteration your task splits into two or more similar tasks".

Nice link discussing recursion: https://stackoverflow.com/questions/126756/examples-of-recursive-functions#