Unit 08: Recursion

  1. Introduction
  2. Examples in math
  3. Generalizing for any n!
  4. Generalizing summation 1
  5. Generalizing summation 2
  6. Example coding videos

  7. Example code and additional resources

This week's stuff:

Introduction

  • Recursion is a manner of solving a problem by breaking it down into smaller pieces - and those smaller pieces are all solved in the same way.


  • I imagine talking to a kid that asks a lot of questions, and just being obstinate when answering those questions:

    1. Kid: "What is n! ?"
    2. Me: "Well, it's n times (n-1)!"
    3. Kid: "OK well what's (n-1)! ?"
    4. Me: "It's (n-1) times (n-2)!"
    5. Kid: "OK well what's (n-2)! ?"
    6. And so on...


  • Each recursive function must have at least one terminating case (where the repetition ends) and at least one recursive case (where we loop by calling the same function again, but with tweaked arguments.)

Examples in math

Factorial:

Summation:

Generalizing for any n!

With our factorial, once we write out all of the steps we can hopefully begin to see a pattern:

  • 4! = 4 * 3!
  • 3! = 3 * 2!

This shows the Recursive Cases of the problem solving approach. Instead, let's think of it in terms of a variable n...

n! = n * (n-1)!


Then, our terminating case here is when we finally stop repeating... In this case, when we hit 1!:

1! = 1

Note that for a factorial, someone might ask "1!" or "0!", so I tend to make two terminating cases: if n == 1 or if n == 0 then we return 1.

Generalizing summation

We use this approach as well for something like the summations...

Figuring out the recursive case...


  • The sum of i from i = 1 to 6 is 6 + the sum of i from i=1 to 5.

  • The sum of i from i = 1 to 5 is 5 + the sum of i from i=1 to 4.

  • The sum of i from i = 1 to n is n + the sum of i from i=1 to (n-1).

The terminating case...


  • The sum of i from i=1 to 1 is 1 (where we're plugging in 1 to i)

Generalizing summation

We can translate these rules into code:

  • Terminating case:

    The sum of i from i=1 to 1 is 1 (where we're plugging in 1 to i)

  • Recursive case:

    The sum of i from i = 1 to n is n + the sum of i from i=1 to (n-1).

  • Code:
    int Sum( int n )
    {
        if ( n == 1 ) { return 1; }    // Terminating case
        return n + Sum( n-1 );         // Recursive case
    }
                    

Example coding videos

SummationDraw lineCount up
Direct link: https://youtu.be/hoAx5JPjMh0 Direct link: https://youtu.be/EAD-GVFVhWs Direct link: https://youtu.be/5ULYCG1UZCY

Example code and additional resources

Example code: (repository)

  1. Draw line
  2. Stop hitting yourself
  3. Summing numbers
  4. Firing employees

  5. Archived videos and class lectures:


    Spring 2024