14: Recursion and Project Design

General Information

Housekeeping

Announcements

See Announcements link in Canvas to keep up with what is going on. Here are a few for review:

Dropping with an EW this Semester

Questions from last class or reading?

Homework Questions?

14.1: Cooperative Quizzes

Quiz Part 1: Individual Readiness Assessment

Quiz Part 2: Team Readiness Assessment (15m)

Quiz Appeals

14.2: Reviewing Functions

Reviewing Function Definitions

Function Call and Return

Image
Stack: source Wikibooks

How Functions Work

Image
Source: YouTube

Call Stack Function call
Return address: OS
local variables:
int total
main()
call add(4, 8)
(click Down arrow)

More Information

Exercise 14.2: Coding a Function (7m)

In this exercise we write a simple function that we will later convert to a recursive function.

For this exercise we break into teams. Within the team, work with each other to develop a solution.

Specifications

  1. Start Repl.it and copy the following code into the code editor.
    #include <iostream>
    using namespace std;
    
    int main() {
        // Enter your code here
    
        return 0;
    }
    
  2. Add the following function prototype before main():
    /**
        Calculates x to the y power (x^y) for positive exponents.
    
        @param x the base
        @param y the exponent
        @return the power of x to the y.
    */
    int power(int x, int y);
    
  3. Write the definition (implementation) of the above function after main() and use a loop for the calculation.
  4. Compile and run your code to make sure wrote the code correctly.

    When you run the program, the output should look like:

    Enter the base: 2
    Enter the exponent: 3
    2^3 = 8
    

    Ask the user for the values of both base and exponent in main(), call the function and print the returned the result.

  5. Once satisfied with your code, copy it into a text editor, save the file as "funpower.cpp", and submit the file to Canvas with the rest of the exercise files for the week.

When finished developing your code click hereClick to show answer to verify. Code need not look exactly the same. After you have completed your own program, reviewing another is often helpful in learning how to improve your programming skills.

14.3: Reviewing Recursion

Recursion is interesting

The Most Interesting Man in the
World's Secret Power: Recursion

About Recursion

Recursion: an approach to problem solving where an algorithm breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems.

Recursion Example: Many Hands Make Light Work

Algorithm For Washing Dishes

Recursive Elements

Reviewing Recursive Functions

Example Code with a Recursive Function (Repl.it)

#include <iostream>
using namespace std;

void wash(int count);

int main() {
    int count;
    cout << "How many dishes to wash? ";
    cin >> count;
    wash(count);
}

void wash(int count) {
    if (count == 0) { // base case stopping condition
        cout << "Done washing dishes\n";
        return;
    }
    // recursive step
    cout << count << " dishes to wash." << endl;
    // solve part of the problem
    count = count - 1; // closer to answer is smaller problem
    wash(count); // recursive function call
    // after the recursive function call
    cout << "Washed " << count << " dishes so far." << endl;
    return; // optional for void functions
}

Exercise 14.3: Coding a Recursive Function (6m)

In this exercise we code.

For this exercise we break into teams. Within the team, work with each other to develop a solution. When the team has finished, choose one member to show your solution to the class by sharing your screen. The instructor will ask one team to share their solution.

Specifications

  1. Start Repl.it and copy the following code into the code editor.
    #include <iostream>
    using namespace std;
    
    int main() {
        // Enter your code here
    
        return 0;
    }
    
  2. Add a stub for a function named rec with the following prototype:
    void rec(int num);
    
  3. Within main() add the following code to call the rec() function:
    int num;
    cout << "What number to count from? ";
    cin >> num;
    rec(num);
    
  4. In the rec() function, add code to print the numbers from num to 0 recursively. Do NOT use a loop statement.

    Hint: Look at the code for the washing dishes example by clicking here. Click here

  5. Compile your code to make sure it has correct syntax. Run the code and verify you see:
    What number to count from? 5
    5
    4
    3
    2
    1
    0
    
  6. Once satisfied with your code, copy your code into a text editor, save the file as "recursion.cpp", and submit the file to Canvas with the rest of the exercise files for the week.

When finished developing your code click hereClick to show answer to verify. Code need not look exactly the same. After you have completed your own program, reviewing another is often helpful in learning how to improve your programming skills.

14.4: How Recursion Works

Reviewing How Recursion Works

Function Call Stack

Call Stack for wash(3)

call stack diagram

Video: Data Structures Using C++: Illustration of Recursive Function Calls (Call Stack)

Pre- and Post-Recursion

Combining Pre-recursion into the Recursive Function Call

Exercise 14.4: Coding Pre- and Post-Recursion (10m)

In this exercise we explore pre- and post-recursion together.

Specifications

  1. Start Repl.it and copy your completed code from the last exercise into the code editor.
  2. Combine the pre-recursion into the function call like we did with wash()
    //count = count - 1;
    wash(count - 1);
    
  3. Compile and run your code to verify the output of this code change does not change the program output.
    What number to count from? 3
    3
    2
    1
    0
    
  4. After the recursive call, add a print statement to display the value of num like:
    cout << num << endl;
    
  5. Compile and run your code to see the output of this post recursion statement. Output should look like:
    What number to count from? 3
    3
    2
    1
    0
    0
    1
    2
    3
    
  6. Once satisfied with your code, copy your code into a text editor, save the file as "prerecpost.cpp", and submit the file to Canvas with the rest of the exercise files for the week.

When finished developing your code click hereClick to show answer to verify. Code need not look exactly the same. After you have completed your own program, reviewing another is often helpful in learning how to improve your programming skills.

14.5: Project Design and Prototype Review

Before the Class Meeting

Arranging the Reviews

During the Review