13. Recursion

Review Topics


General Information

Housekeeping

  • Make sure you follow along with this page linked in Canvas
  • Please keep your microphone off unless you are asking a question
  • Please turn on camera if you can (optional)
  • Use chat if you would like to comment or ask questions

Announcements

See Announcements link in Canvas for course information. Here are some other reminders:

  • Career fairs in April, see Career Services
  • Remember that PAs and the Individual Readiness Assurance Quiz are due before class on Tuesday.
  • Remember to post in the Pair programming partners discussion group if you need a partner
  • Remember that the exercises from this page are due Sunday at 9:00pm.
  • Remember that CAs, Labs, and Class Exercises may be completed up to two days late but with a 10%/day penalty.
  • Remember that some lab solutions are posted in Canvas Modules
  • Cabrillo College is allowing students to select the P/NP option by the grade deadline for the term
  • Free Fresh Market schedule: free fresh fruits and vegetables
  • Food & Housing Resources: free food, meals, temporary and permanent housing
  • COVID-19 Resources and Information: Includes loaner-laptop information
  • Campus WiFi Access
    • Aptos: parking lots K and L on this Cabrillo Aptos Map
    • Watsonville: parking lot at Watsonville Center

Homework Help

What to take next?

13.1: Readiness Assessment Quizzes

  • Reading and participation activities are due before the first class meeting of the week
  • Quizzes assess the comprehension of the reading and participation activities

Quiz Part 1: Individual Readiness Assessment

  • Complete this quiz solo to assess your reading comprehension and readiness
  • Must take this quiz before the first class meeting of the week to ensure you are ready for the team quiz
  • Cannot take the quiz late
  • Quiz is open book and notes but timed
  • Highest score is counted so take the quiz multiple times

Quiz Part 2: Team Readiness Assessment (20m)

  • Must attend the class meeting to take this quiz
  • Login to Canvas and enter the access code
  • Will move to breakout rooms with your team
  • Make sure you have the access code for the exam
  • Openly discuss what you believe to be the best answers for the questions
  • Decide how to agree on the answers
    • Strive to reach a consensus on quiz answers
    • If no consensus, work it out as you and others in your group see fit
  • Turn in the quiz as a group
  • Each group member will receive the same score
  • Return to the main meeting room when finished

Quiz Appeals

  • After completing the team quiz, team members may appeal an answer
  • Appeals can be based on two criteria:
    1. Question is factually wrong

      Appeal must included citations to sources of information that document or support an alternative answer. Team may access reference materials during the appeal.

    2. Question is confusing based on it's wording

      Appeal must include an appropriate rewrite of questions or answers that you interpret as ambiguous or confusing.

  • Work with teammates to develop and write any appeals
  • Team has up to 24 hours after the quiz to email appeal to instructor
  • If appeal is granted, only the teams that submitted appeal gets credit

13.2: Sampler Project

The sampler project is a way to demonstrate what you have learned about C++ by using most of the coding techniques we have covered during the course. It is also a chance to explore how to apply coding to your interests.

Developing a project is a powerful way to develop a deeper understanding of programming. You can dig deeper into things that interest you. At the end you will have developed a program that you can be proud of and list as one of your accomplishments.

For the sampler project, pair-programming is optional. If not pair programming then you may not give or receive code from any other person as outlined in the Academic Integrity policy of the syllabus.

Whether pair programming or not do not copy or modify code from the internet or other sources without attribution.

  • Any copied code should be less than 10 lines with a note of where it came from, like the internet address (URL).
  • Copying code from the instructor's lesson examples or textbook without attribution is allowed.

If you need help finding a partner, please post in the Pair Programming Discussion.

Starting the Project

You will review your product design and demonstrate your prototype to me personally on Thursday next week. I will provide guidance on finishing your final version of the project well.

To get started on designing your project, read the sampler specifications. After reading the specification, you develop a project design and prototype, which are due next week on Thursday at the start of class (no lates).

After the initial review, you will complete your project and demonstrate it during the last class meeting. You may present your final project earlier, if you like, for extra credit.

13.3: Finishing File I/O

To finish file I/O we continue from where we left off in lesson 12.

13.4: Reviewing Functions

In this section we review functions as preparation for recursion.

Reviewing Function Definitions

  • Functions are a way to organize code into modules
  • Each function defines a module--independent unit used to construct a program
  • To define a function, we use the following syntax:
    returnType functionName(parameter1, ..., parametern) {
        statements
    }
    
  • Where:
    • returnType: the data type of the value returned (void for returning nothing)
    • functionName: the name made up for the function
    • parameterx: the input values of the function, if any
    • statements: the statements to execute when calling the function
  • As an example, we wrote the function:
    int add(int a, int b) {
        int c = a + b;
        return c;
    }
    
  • Functions returning a value use a return statement
    return sum;
    
  • A return statements ends a function call and returns a value specified after the word return

Function Call and Return

  • When we define a function, the code does not execute automatically
  • To execute the code, we must call a function like:
    int total = add(4, 8);
    
  • Before executing the function, the program copies arguments to parameter local variables and stores a return address
  • The function executes and then stores the result in the return value location
  • When the called function finishes executing it returns to the previously-stored return address
  • Then an instruction, as coded, copies the function's return value to the appropriate variable
  • After the return, the calling code continues by executing the next operation

Image
Stack: source Wikibooks

How Functions Work

  • Each function call creates a new set of local variables.
  • Each return causes those local variables to be discarded.
  • The computer manages function calls through a call stack
  • A call stack is a stack data structure that stores data about active functions
  • The data for a call stack is stored in a series of stack frames
  • A stack frame, also known as an activation record, is the data for one function call
  • A stack frame generally includes the following:
    • The return address
    • Argument and local variables
  • When calling a function, new space is allocated for the above data
  • When a function returns from a call, the frame data is deleted

Image
Source: YouTube

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

More Information

  • Zybook 8.6: How functions work
  • Zybook 13.6: Stack overflow

Exercise 13.4: 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 Replit 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.

13.5: Reviewing 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 is interesting

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

About Recursion

  • Recursion is a natural approach to some problems
  • It allows us to break down a problem into one or more subproblems similar in form to the original problem
  • Recursion divides the problem into two parts:
    • Recursive step
    • Base case
  • The recursive step solves part of the problem and then recurs to repeat the process
  • Since the recursive step solves part of the problem, the problem is smaller problem in the next step
  • Eventually the smaller problem becomes easy enough to just solve
  • The easy-to-solve problem is known as the base case

Recursion Example: Many Hands Make Light Work

  • What if you were asked to do some repetitive task like washing the dishes?
  • You look at the pile of dishes and realize you have better things to do
  • So you wash one set of dishes and then ask someone else to wash the dishes
    • Then you leave as soon as possible
  • The next person notices your actions and decides to do the same
  • They wash one set of dishes and then ask someone else to wash the remaining dishes
  • This sequence repeats until all the dishes are washed and the sink is empty
  • Writing this as an algorithm, we have:

Algorithm For Washing Dishes

  • If the sink is empty, do nothing
  • Else:
    • Wash a set of dishes
    • Ask someone else to wash the remaining dishes

Recursive Elements

  • Notice the recursive nature of the algorithm
  • The "else" clause recurs (occurs again repeatedly):
    • To do the dishes, we ask someone else to do the dishes
  • To make sure this algorithm is not an endless passing of the buck, each recursive step does some work
  • This makes the job passed to the next person smaller
  • When all the dishes are done, the process of asking someone else to do the dishes ends because the sink is empty

Reviewing Recursive Functions

  • Now that we see how recursion works, let us look at how to implement it in a program
  • We implement recursion in C++ using functions
  • Each function contains a conditional statement
  • One of the statements contains a call to the same function
  • Here is a c common recursive structure:
    returnType recursiveFunction(parameters) {
        if (stopping condition) { // base case
            // Problem is very easy
            // so solve it and return
        }
        // recursive step
        // solve part of the problem
        // leaving a smaller problem
        recursiveFunction(arguments);
        // after the recursive function call
        return xxx; // depending on return type
    }
    
  • Like a loop, a recursive function must have some way to end
  • We often write the base case first and the recursive step second
  • The code below implements our recursive example

Example Code with a Recursive Function (Replit)

#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 13.5: Coding a Recursive Function (6m)

In this exercise we code a recursive function.

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 Replit 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 if it functions correctly and uses recursion. After completing your own program, reviewing another is often helpful in learning how to improve your programming skills.

13.6: How Recursion Works

Reviewing How Recursion Works

  • To understand how recursion works, we must consider a data structure known as a stack
  • A stack is like a pile of dishes:

    A stack of dishes

  • When a dish is placed on the stack, it is placed on top
  • Similarly, when a dish is removed from the stack, it is taken from the top
  • The last dish put on the stack is the first dish removed from the stack:
    • Otherwise you get a lot of broken dishes

Function Call Stack

  • Whenever we call a function, the computer sets aside a block of memory for that function
  • The memory is used to store the local variables and return address
  • The return address is the point in the code immediately after where the function was called
  • This memory is allocated in an area of the computer known as the call stack
  • The information saved is known as the stack frame or activation record
  • Every function call creates a new stack frame
  • Every time a function returns, the stack frame data is popped off the 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

  • Remember the structure of the recursive case in our dish washing example
    cout << count << " dishes to wash." << endl;
    count = count - 1;
    wash(count); // recursive call
    cout << "Washed " << count << " dishes so far.\n";
    
  • Before the recursive call are statements showing the number of dishes to wash
    cout << count << " dishes to wash." << endl;
    
  • Next some work was done to solve part of the problem:
    count = count - 1;
    
  • Then comes the recursive call:
    wash(count); // recursive call
    
  • After the recursive call another statement is executed:
    cout << "Washed " << count << " dishes so far." << endl;
    
  • Within the recursive case, code executed before the recursive call is known as pre-recursion
  • Code executed after the recursive call is known as post-recursion

Combining Pre-recursion into the Recursive Function Call

  • We could combine some pre-recursion into the actual function call
  • Instead of:
    count = count - 1;
    wash(count);
    
  • We code:
    wash(count - 1);
    
  • This works because the calculation (count - 1) occurs before the function call

Exercise 13.6: Coding Pre- and Post-Recursion (5m)

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

Specifications

  1. Start Replit 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.

13.7: Developing a Recursive Algorithm

In this section we look at how to develop a recursive algorithm to solve a problem.

13.7.1: About Recursive Algorithms

  • Before we write recursive functions, we must develop a recursive algorithm
  • To develop a recursive algorithm, we must find a way to do the following:
    1. Use a solution to a smaller or easier version of a problem to arrive at the solution itself
    2. Know when the problem is small enough to solve directly
  • As another example of recursion, let us look at exponentiation
  • We will limit ourselves to positive integers
  • The mathematical notation for exponentiation is:

    xy

  • A function prototype for exponentiation could be:
    int power(int x, int y);
    
  • The base case for exponentiation is when y == 0:

    x0 = 1

  • The definition of exponentiation when y is a positive integer is:

    xy = 1 * x * x * x ... (y times)

  • As we can see, the operation corresponds to repeated multiplication
  • Another way to express the operation is as a recurrence relation

    xy = x * xy - 1

  • The recurrence relation shows the recursive step we need for our algorithm
  • The base case for the

Thinking Recursively

  • We start developing the algorithm by working through the process by hand
  • It seems like a lot of work, and so we consider how to get someone else to do most of the work
  • If we could get someone else to calculate xy - 1, we could just multiply by x one time
  • This process could repeat until we are done
  • How would we know when we were done?

Recursive Algorithm For Exponentiation

  • If y is 0, we are done and the result is x0, which is 1
  • Else (while y = 1):
    • Get the value of xy - 1
    • Multiply the result of xy - 1 times x

13.7.2: Creating a recursive function

We may create a recursive function in two steps:

  1. Write the base case
  2. Write the recursive case

Every recursive function must have a base case that returns a value without performing a recursive call.

  • A programmer may write the base case first, and then test
  • Some problems may need more than one base case
  • When satisfied, write the recursive case

Exercise 13.7: Coding a Recursive Algorithm (10m)

In this exercise we translate a resursive algorithm into code.

Specifications

  1. Start Replit and copy the following code into the code editor.
    #include <iostream>
    using namespace std;
    
    int power(int x, int y) {
        // Add code here
        return 0; // dummy return value
    }
    
    int main() {
        int x = 0, y = 0;
        cout << "Enter the base: ";
        cin >> x;
        cout << "Enter the exponent: ";
        cin >> y;
        cout << x << "^" << y << " = " << power(x, y) << endl;
        return 0;
    }
    
  2. In the power function, add code to test for the base case and to return an appropriate value. When run, the output should look like:
    Enter the base: 2
    Enter the exponent: 0
    2^0 = 1
    
  3. Review the recurrence relationship and code the recurrence relation:

    xy = x * xy - 1

  4. When run, the output should look like:
    Enter the base: 2
    Enter the exponent: 3
    2^3 = 8
    
  5. Once satisfied with your code, copy your code into a text editor, save the file as "recpower.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.

Last Updated: May 05 2021 @19:40:41