CS210 · Annotated SlidesRecursion — Recursion
Recursion · Annotated slides

Recursion

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

Slide text Study notes Highlight: key words Tips, tricks & traps Seen again elsewhere How it can come up

Recursion

1
Slide 2: when we loop
Exam weight Low
    Slide 3: forward calls
    Exam weight Low
      Slide 4: runtime
      Exam weight Low
        Slide 5: Example: English Ruler
        Exam weight Low
        1. English ruler: drawInterval(L) = drawInterval(L−1), a tick of length L, drawInterval(L−1).
        Slide 6: Using Recursion
        Exam weight Low
          Slide 7: Recursive Drawing Method
          Exam weight Low
            Slide 8: A Recursive Method for Drawing Ticks on an English Ruler
            Exam weight Low
              Slide 9: 17
              Exam weight Low
                Slide 10: Visualizing Binary Search
                Exam weight Low
                1. Binary search halves the search range each call.
                Slide 11: Slide 11
                Exam weight Low
                  Slide 12: Analyzing Binary Search
                  Exam weight High
                  1. Binary search runs in O(log n).
                  🎯 How this can come up · 1 question
                  MCQ

                  Binary search on a sorted array of n elements is:

                  Linear Recursion

                  Test for base cases

                  Begin by testing for a set of base cases (there should be

                  at least one).

                  Every possible chain of recursive calls must eventually

                  reach a base case, and the handling of each base case should not use recursion.

                  Recur once

                  Perform a single recursive call

                  This step may have a test that decides which of several

                  possible recursive calls to make, but it should ultimately make just one of these calls Define each possible recursive call so that it makes

                  progress towards a base case.

                  © 2014 Goodrich, Tamassia, Goldwasser

                  Recursion

                  13
                  Exam weight Low
                  1. Linear recursion: at most one recursive call per invocation (sum, reverse array).
                  Slide 14: Slide 14
                  Exam weight Low
                    Slide 15: Example of Linear Recursion
                    Exam weight Low
                      Slide 16: swap www
                      Exam weight Low
                        Slide 17: Defining Arguments for Recursion
                        Exam weight Low
                          Slide 18: I
                          Exam weight Low
                            Slide 19: i
                            Exam weight Low
                              Slide 20: Recursive Squaring Method
                              Exam weight Medium
                              1. Recursive squaring: xⁿ = (x^(n/2))² → O(log n) multiplications.
                              Slide 21: Analysis
                              Exam weight Low
                                Slide 22: Tail Recursion
                                Exam weight Low
                                1. Tail recursion: the recursive call is the last step → easy to convert to a loop.
                                Slide 23: Binary Recursion
                                Exam weight Low
                                1. Binary recursion: two recursive calls per non-base case.
                                Slide 24: n
                                Exam weight Low
                                  Slide 25: Computing Fibonacci Numbers
                                  Exam weight High
                                  1. Naïve Fibonacci (binary recursion) is exponential: it recomputes the same values.
                                  🎯 How this can come up · 1 question
                                  True / False

                                  The naïve recursive Fibonacci runs in linear time.

                                  Slide 26: Analysis
                                  Exam weight Low
                                    Slide 27: A Better Fibonacci Algorithm
                                    Exam weight Low
                                    1. Better Fibonacci returns a pair (F(k), F(k−1)) → linear recursion, O(n).

                                    Jan

                                    2call

                                    more

                                    Multiple Recursion

                                    Motivating example:

                                    summation puzzles

                                    pot pan bib

                                    +

                                    =

                                     

                                    dog cat pig

                                    +

                                    =

                                    boy girl baby

                                    +

                                    =

                                    Multiple recursion:

                                    makes potentially many recursive calls

                                    not just one or two

                                    © 2014 Goodrich, Tamassia, Goldwasser

                                    Recursion

                                    28
                                    Exam weight Low
                                      Slide 29: Algorithm for Multiple Recursion
                                      Exam weight Low
                                        Slide 30: Example
                                        Exam weight Low
                                          Slide 31: Visualizing PuzzleSolve
                                          Exam weight Low