CS210 · Recursion · Annotated SlidesRecursion
Original
Overview

Recursion

Factorial, the English ruler, binary search and its analysis, linear, tail, binary and multiple recursion, recursive squaring, and Fibonacci (bad vs. good).

How to read this page

Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.

All 31 slides
  1. 1 Recursion
  2. 2 when we loop
  3. 3 forward calls
  4. 4 runtime
  5. 5 Example: English Ruler
  6. 6 Using Recursion
  7. 7 Recursive Drawing Method
  8. 8 A Recursive Method for Drawing Ticks on an English Ruler
  9. 9 17
  10. 10 Visualizing Binary Search
  11. 11 Slide 11
  12. 12 Analyzing Binary Search
  13. 13 Linear Recursion
  14. 14 linear I
  15. 15 Example of Linear Recursion
  16. 16 swap www
  17. 17 Defining Arguments for Recursion
  18. 18 I
  19. 19 i
  20. 20 Recursive Squaring Method
  21. 21 Analysis
  22. 22 Tail Recursion
  23. 23 Binary Recursion
  24. 24 n
  25. 25 Computing Fibonacci Numbers
  26. 26 Analysis
  27. 27 A Better Fibonacci Algorithm
  28. 28 Jan
  29. 29 Algorithm for Multiple Recursion
  30. 30 Example
  31. 31 Visualizing PuzzleSolve
Slide 1 / 31

Recursion

Slide 1: Recursion
Slide 2 / 31

when we loop

Slide 2: when we loop
Slide 3 / 31

forward calls

Slide 3: forward calls
Slide 4 / 31

runtime

Slide 4: runtime
Slide 5 / 31

Example: English Ruler

Slide 5: Example: English Ruler

Notes

  1. English ruler: drawInterval(L) = drawInterval(L−1), a tick of length L, drawInterval(L−1).

Slide 6 / 31

Using Recursion

Slide 6: Using Recursion
Slide 7 / 31

Recursive Drawing Method

Slide 7: Recursive Drawing Method
Slide 8 / 31

A Recursive Method for Drawing Ticks on an English Ruler

Slide 8: A Recursive Method for Drawing Ticks on an English Ruler
Slide 9 / 31

17

Slide 9: 17
Slide 10 / 31

Visualizing Binary Search

Slide 10: Visualizing Binary Search

Notes

  1. Binary search halves the search range each call.

Slide 11 / 31

Slide 11

Slide 11: Slide 11
Slide 12 / 31

Analyzing Binary Search

Slide 12: Analyzing Binary Search

Exam angle

PredictionQ1

Binary search on a sorted array of n elements is:

Slide 13 / 31

Linear Recursion

Slide 13: Linear Recursion

Notes

  1. Linear recursion: at most one recursive call per invocation (sum, reverse array).

Slide 14 / 31

linear I

Slide 14: linear I
Slide 15 / 31

Example of Linear Recursion

Slide 15: Example of Linear Recursion
Slide 16 / 31

swap www

Slide 16: swap www
Slide 17 / 31

Defining Arguments for Recursion

Slide 17: Defining Arguments for Recursion
Slide 18 / 31

I

Slide 18: I
Slide 19 / 31

i

Slide 19: i
Slide 20 / 31

Recursive Squaring Method

Slide 20: Recursive Squaring Method

Notes

  1. Recursive squaring: xⁿ = (x^(n/2))² → O(log n) multiplications.

Slide 21 / 31

Analysis

Slide 21: Analysis
Slide 22 / 31

Tail Recursion

Slide 22: Tail Recursion
Slide 23 / 31

Binary Recursion

Slide 23: Binary Recursion
Slide 24 / 31

n

Slide 24: n
Slide 25 / 31

Computing Fibonacci Numbers

Slide 25: Computing Fibonacci Numbers

Notes

  1. Naïve Fibonacci (binary recursion) is exponential: it recomputes the same values.

Exam angle

PredictionQ1

The naïve recursive Fibonacci runs in linear time.

Slide 26 / 31

Analysis

Slide 26: Analysis
Slide 27 / 31

A Better Fibonacci Algorithm

Slide 27: A Better Fibonacci Algorithm
Slide 28 / 31

Jan

Slide 28: Jan
Slide 29 / 31

Algorithm for Multiple Recursion

Slide 29: Algorithm for Multiple Recursion
Slide 30 / 31

Example

Slide 30: Example
Slide 31 / 31

Visualizing PuzzleSolve

Slide 31: Visualizing PuzzleSolve