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."