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

12.1 Material

A non-programming example

An iterative solution converted to recursion

Structure of recursive solutions

Section 12.2: Better Example of Recursion

12.2 Material

Mechanics of recursion

Section 12.3: Recursive Functions and Data

12.3 Material

Integer exponentiation

Greatest common divisor

Directory crawler

Helper methods

Section 12.5: Recursive Backtracking

12.5 Material

A simple example: traveling north/east

8 Queens Puzzle

Solving Sudoku puzzles

Section 12.6: Case Study: Prefix Evaluator

12.6 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 Homework

HW Questions

(Recommended) Self-check problems: #1, #2, #5, #7, #14, #16, #19, #22, #23, #28

(Required) Exercises: #4, #6, #15, #22

(Required) Projects: (none)

HW Details

Self-check:

• 1 - what is recursion
• 2 - base vs recursive case
• 5 - mystery recursion
• 7 - convert to recursive
• 14 - mystery recursion
• 16 - factorial recursion
• 19 - improve factorial recursion
• 22, 23 - backtracking
• 28 - 8 queens problem

Exercises:

• 4 - double digits of number
• 6 - printing list with recursion
• 15 - n pick r n!/(n-r)!
• 22 - backtracking to write integers as sum of unique integer squares

Projects:

• none

Chapter 12 Code

Lecture Code

NEED TO DO ALL OF THIS

Worksheet Code

Sudoku

• Backtrack algorithm
• Give them baseline of reading puzzle in, printing puzzle, doing some logic for checking rows/columns
• They implement the backtrack algorithm

Chapter 12 Goodies

Puzzle 5

Modular arithmetic, multiplicative inverses, importance of prime modulus and factoring

Puzzles/Fall 2016/Puzzle 5

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#