15: Recursion, Finals and Projects

What We Will Cover


Continuations

Questions from last class?

Questions on the Project?

  • Anyone completed their project and ready to present or show it to me early?
  • Do not forget to submit your project before presenting
  • Also make sure you have a printed project report (enhanced README.txt) for me

15.1: Reviewing Functions

Learner Outcomes

At the end of the lesson the student will be able to:

  • Define and call functions
  • Describe the difference between parameters and arguments
  • Identify the scope of a variable
  • Write function declarations (prototypes)
  • Describe function style requirements

15.1.1: Defining and Calling Functions

  • As we add more code to programs, main() becomes too long to easily understand
  • The solution is to break up the long sequences of code into shorter sections using functions
  • Functions are a way to organize programs into modules -- distinct but interrelated parts
  • With functions, we can potentially reduce the size of our code by collecting duplicate code into one place
  • In addition, we can reuse well-developed functions in other programs, saving us from rewriting code

Defining Functions

  • To define a function, we use the following syntax:
    returnType functionName(parameter1, ..., parametern) {
        statements
    }
    
  • Where:
    • returnType: the data type of the value returned
    • 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
  • If the function does not return a value, we use the return type: void
  • Otherwise, we specify the type of data we want to return
  • As an example, we wrote the function:
    int add(int a, int b) {
        int sum = a + b;
        return sum;
    }
    
  • The add() function returns an integer value as shown by the return value: int
  • 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
  • For a void function, we code nothing after the word return, like
    return;
    
  • Return statements are optional for void functions
  • If the return statement is missing, a void function returns automatically after reaching its last line

Function Calls

  • When we define a function, the code does not execute automatically
  • To execute the code, we must call a function like:
    int total = add(32, 10);
    
  • When we call a function, we specify its name and provide arguments for each parameter
  • The flow of the program execution stops and jumps to the called function
  • When the called function finishes executing it returns
  • After the return, the calling code continues by executing the next operation

Example Program with a Second Function

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

int add(int a, int b) {
    int sum = a + b;
    return sum;
}

int main() {
    cout << "Enter two numbers to add: ";
    int num1, num2;
    cin >> num1 >> num2;
    int total = add(num1, num2);
    cout << "Sum=" << total << endl;

    return 0;
}

Image
Stack: source Wikibooks

Function Call Stacks

  • One question remaining is how the computer manages function calls
  • The computer manages function calls through a call stack
  • A call stack is a stack data structure that stores data about the 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
Call Stack Function call
Return address: OS
local variables:
int total
main()
call add(2, 3)
(click)

Check Yourself

  1. The following code snippet displays the value ________.
    int fun() {
        return 12;
    }
    // other code here
    cout << fun();
    
  2. Which of the following is a function definition and which is a function call?
    1. add(32, 10);
    2. int add(int a, int b) { /* statements */ }
  3. The result of compiling and running the following code snippet is ________.
    void fun() {
        return 12;
    }
    // main code here
    cout << fun();
    
    1. Does not compile
    2. Compiles but does not run
    3. Displays 12 to the terminal window
    4. Displays void to the terminal window
  4. The best return type for a function with the following return statement is ________.
    return "42.3";
    

15.1.2: Parameters and Scope

  • When we define a function, we want it to be reusable
  • To make a function more reusable, we avoid hard-wiring important values
  • Instead, we pass the key values by defining parameters
  • A parameter is a variable that receives information during a function call
  • To identify their special ability, parameters are declared inside the parenthesis () of a function definition
    int add(int a, int b) { /* statements */ }
    
  • When we call a function, we supply an argument for each parameter
    add(32, 10)
    
  • Parameter variables hold the argument values when we call a function

    function parameters

  • In the above, the values of num1 and num2 are copied to the parameters a and b respectively
  • C++ can pass arguments to parameters in the following ways:
  • Because value parameters send a copy of an arguments value, change to parameters have no effect on the argument
  • However, reference parameters send a variable address and thus assignment to the parameter changes the value of the argument variable
  • To make a parameter a reference type, we place an ampersand (&) after the data type like:
    int add(int& a, int& b) { /* statements */ }
    

Local and Global Variables

  • Scope is the term used to define where a program can access a variable
  • A variable declared inside a pair of curly braces is local to that block of code
  • Blocks begin at an opening brace ({) and end at a closing brace (})
  • Global variables are declared outside of any block
  • Local variables take precedence over global variables with the same name
  • One may be tempted to use global variables to avoid parameters
  • Global variables are syntactically correct but experience has shown them to be problematic
  • If many parts of a program access global variables, it becomes hard to reason about program correctness
  • Thus we should NOT use global variables in this course
  • Global constants, on the other hand, are an acceptable way to declare constants used throughout a program

Check Yourself

  1. The following code displays the value ________.
    int fun(int param) {
        param = 45;
        return param - 3;
    }
    // main code here
    int x = 7;
    cout << fun(x);
    
  2. The following code displays the value ________.
    int fun(int param) {
        param = 42;
        return param - 3;
    }
    // main code here
    int x = 7;
    fun(x);
    cout << x;
    
  3. The following code displays the value ________.
    int fun(int& param) {
        param = 42;
        return param - 3;
    }
    // main code here
    int x = 7;
    fun(x);
    cout << x;
    
  4. The following code displays the value ________.
    int x = 21; // the problem with global variables
    int fun(int& x) {
        x = 42;
        return x - 3;
    }
    // main code here
    x = 7;
    int x = 3;
    x = fun(x);
    cout << x;
    

15.1.3: Prototypes, Terminology and Style

  • C++ allows you to declare functions without defining them
  • Function declarations (prototypes) have the function heading without the function body
  • The general syntax for declaring a function is:
    returnType functionName(parameter1, ..., parametern);
    
  • For example:
    void getProduct(string& name, double& price);
    
  • Prototypes end with a semicolon (;) rather than curly braces
  • By declaring prototypes before main() we can define the functions after main()
  • This is important when functions call each other in a circular manner
  • Function prototypes also allow use to declare functions in one file and definitions in another file

Some Function Terminology

  • function declaration: tells the compiler the function name, parameter types and return type only
  • function definition: where the actual code for the function is written
  • prototype: another term for function declaration
  • implementation: another term for function definition
  • overloaded function: two functions with same name in the same scope but different parameter types

Function Style

  • Functions have style requirements we must follow
  • For instance, we must have a block comment before the name
  • Functions have naming conventions similar to variable names: camel case or underbars
  • When making up a name for a function, use verbs since functions perform an action
  • We indent functions statements inside curly braces, like elsewhere in our code

Exercise 15.1: Finishing our Function Review (5m)

In this review exercise we finish developing our functions.

  1. Copy the following program into a text editor, save it as funreview.cpp, and then compile and run the starter program to make sure you copied it correctly.
    #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().

    Hint: use a loop for the calculation.

  4. Ask the user for the values of both x and y in main(), call the function and print the returned the result.
  5. Test your code with values like those shown below.
  6. Save your source code file to submit as part of the sampler project.
  7. When finished, please help those around you.

Your completed program should operate like the following.

Enter your name: Puddin Tane
Welcome, Puddin Tane!

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

Text in aqua is the user input and NOT part of the program code.

When finished developing your code click here Click to show answer to compare your solution to mine. After you have completed your own solution, reviewing another is often helpful in learning how to improve your programming skills.

15.2: Introduction to Recursion

Learner Outcomes

At the end of the lesson the student will be able to:

  • Design recursive algorithms
  • Code recursive functions
  • Trace the processing steps of recursive functions
Recursion is interesting

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

15.2.1: About Recursion

Recursion: an approach to problem solving where an algorithm is defined by referring to itself until a specified condition is met.

  • 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
    • Sounds circular, but in practice is not
  • Recursion divides the problem into two parts:
    • Recursive step
    • Base case
  • The recursive step solves part of the problem as defined in a function and then calls the same function
  • Since the recursive step solves part of the problem, it passes a smaller problem to the recursive function
  • 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 we have better things to do
  • So you wash one dish 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 dish and then ask someone else to wash the 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 dish
    • Ask someone else to wash the dishes

Recursive Elements

  • Notice the recursive nature of the algorithm
  • The "else" clause calls itself:
    • 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 person does some work
  • This makes the job passed to the next person smaller
  • When all the dishes are done, the chain of asking someone else to do the dishes is broken

Check Yourself

  1. True or false: a recursive step needs to solve some part of a problem.
  2. The easy-to-solve part of a recursion is know as the ________ case.
  3. True or false: every recursive algorithm must have a base case.

15.2.2: Implementing 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 the same function
  • This structure is shown below:
    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

Implementation of Recursive Example

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#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: Writing a Recursive Function (5m)

  1. Copy the following program into a text editor, save it as recursion.cpp, and then compile and run the starter program to make sure you copied it correctly.
    #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.

  5. Save your code for the next Exercise.
  6. Check to see if the student on either side of you needs help. If so, offer to help them.
  7. Be prepared to answer the following questions.

When finished developing your code click here Click to show answer to compare your solution to mine. After you have completed your own solution, reviewing another is often helpful in learning how to improve your programming skills.

Check Yourself

  1. True or false: Recursion is a form of looping but without using a loop statement.
  2. Recursion is implemented in C++ using if-statements and ________.
  3. In recursive algorithms, an if-statement is needed to test for the ________ case.
  4. What are the elements of using recursion to loop?

15.2.3: 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)

Check Yourself

  1. Items are placed on the top of a stack and removed from the ________.
  2. True or false: the last item placed on a stack is the first item removed.
  3. Functions are tracked on a call stack with a stack ________.
  4. True or false: a function on a call stack is active and has yet to complete execution.

15.2.4: 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) is made before the function call

Some Recursion Terminology

Some commonly used recursion terms

Exercise: Exploring Pre- and Post-Recursion (2m)

  1. Start with your code from the last Exercise: Writing a Recursive Function.
  2. Combine the pre-recursion into the function call
    //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.
  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. Save your code as an example for the next Exercise.
  7. When finished, please help those around you.
  8. Be prepared to answer the following Check Yourself questions when called upon.

When finished developing your code click here Click to show answer to compare your solution to mine. After you have completed your own solution, reviewing another is often helpful in learning how to improve your programming skills.

Check Yourself

  1. True or false: within the recursive step, code executed before the recursive call is known as pre-recursion.
  2. Within the recursive step, code executed after the recursive call is known as ________ recursion.
  3. In the following recursive code, the pre-recursion calculation is ________.
    void rec(int num) {
        if (num <= 0) {
            cout << num << endl;
            return;
        }
        cout << num << endl;
        rec(num - 1);
        cout << num << endl;
    }
    
  4. In the above recursive code, the post-recursion statement is ________.
  5. What is the effect of pre-recursion vs. post-recursion?

15.2.5: Developing a Recursive Algorithm

  • 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 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

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):
    • Ask someone else to compute xy - 1
    • We multiply the result of xy - 1 times x

Activity: Calculating 2x

  1. For this activity we will calculate 2x using the power of student brains.
  2. You will be asked for the answer to 2x, where x is an integer value.
  3. If the value of x is one or less then say the answer.

    For example, say: "21 is 2."

  4. Otherwise, ask the student next to you for the value of 2x - 1

    For example, if you were asked for 214 , ask the student next to you: "What is 213?"

  5. When you get an answer to your question, double it and say the answer out loud.

    For example, if you get an answer to 213, say: "214 is 16,384."

Check Yourself

  1. True or false: exponentiation with positive integers corresponds to repeated multiplication.
  2. The following is known as a ________ relation.

    xy = x * xy - 1

  3. The base case of our recursive algorithm occurs when y is equal to ________.

15.2.6: Coding the Recursive Algorithm

  • Implementing a recursive algorithm is usually straightforward

Example Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

int power(int x, int y);

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;
}

int power(int x, int y) {
    if (y == 0) {
        return 1;
    }
    y = y - 1;
    int result = power(x, y);
    result = result * x;
    return result;
}

Tracing the Structure

  • Which line of code in the above is the recursive call? Click
  • Which line(s) of code is the base case? Click

Tracing the Execution

  • To see how a recursive function works, we can add print statement to trace the flow
  • As an example, we trace power(2, 3) called from main():
    main() calls power(2, 3)
      power(2, 3) calls power(2, 2)
        power(2, 2) calls power(2, 1)
          power(2, 1) calls power(2, 0)
            power(2, 0) returns 1 (base case)
          power(2, 1) returns 2
        power(2, 2) returns 4
      power(2, 3) returns 8
    power(2, 3) returns 8 to main()
    
  • Note that the first half of the trace makes successive function calls
    • Until the base case is reached
  • The second half returns the values from the recursive calls

Instrumented Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
using namespace std;

int power(int x, int y);

int main() {
    int x = 0, y = 0;
    cout << "Enter the base: ";
    cin >> x;
    cout << "Enter the exponent: ";
    cin >> y;
    cout << "main() calls power(" << x << ", " << y << ")\n";
    cout << "power(" << x << ", " << y << ") returns "
         << power(x, y) << " to main()\n";
    return 0;
}

int power(int x, int y) {
    if (y == 0) {
        cout << "power(" << x
             << ", 0) returns 1 (base case)\n";
        return 1;
    }
    cout << "power(" << x << ", " << y << ") "
         << "calls power(" << x << ", "
         << (y - 1) << ")\n";
    y = y - 1; // pre-recursion
    int result = power(x, y); // recursion
    result = result * x; // post-recursion
    cout << "power(" << x << ", " << (y + 1)
         << ") returns " << result << endl;
    return result;
}

Check Yourself

  1. When a recursive function calls itself, that step known as the ________ step.
  2. True or false: the base case always includes a recursive function call.
  3. True or false: the recursive step must always define a task that is easier, smaller or closer to completion than the original task.
  4. In the following recursive code, the pre-recursion calculation is ________.
    int power(int x, int y) {
        if (y == 0) {
            return 1;
        } else {
            int result = power(x, y - 1);
            return x * result;
        }
    }
    
  5. In the above recursive code, the post-recursion calculation is ________.

15.2.7: Using Recursion with Input Validation

Example of Input Validation Function with Loop

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
using namespace std;

// Function to read a double
double readNumber(string prompt) {
    double input = 0.0;
    bool isError = true;
    do {
        cout << prompt;
        cin >> input;
        if (cin.fail()) {
            cout << "Please enter numbers only!\n";
            cin.clear();
            cin.ignore(1000, '\n');
        } else {
            isError = false;
        }
    } while (isError);
    return input;
}

// Main function for testing.
int main() {
    double num = readNumber("Enter a number: ");
    cout << "You entered: " << num << endl;

    return 0;
}
  • To allow a user to reenter data we coded a loop, else clause and a control variable isError
    double readNumber(string prompt) {
        double input = 0.0;
        bool isError = true;
        do {
            cout << "Enter a number: ";
            double input = 0.0;
            cin >> input;
            if (cin.fail()) {
                cout << "Please enter numbers only!\n";
                cin.clear();
                cin.ignore(1000, '\n');
            } else {
                isError = false;
            }
        } while (isError);
        return input;
    }
    
  • The loop, else-clause and control variable complicate the code
  • We can simplify the code by using recursion instead:
    double readNumber() {
        double input = 0.0;
        cout << "Enter a number: ";
        cin >> input;
        if (cin.fail()) {
            cout << "Please enter numbers only!\n";
            cin.clear();
            cin.ignore(1000, '\n');
            return readNumber();
        }
        return input;
    }
    
  • Notice how much shorter and simpler the code looks
  • The do-while loop and else clause are replaced by a function call
  • All we needed to repeat the input operation when an error occured was one line:
    return readNumber();

Example of Input Validation with Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
using namespace std;

// Recursive function to read a double
double readNumber(string prompt) {
    double input = 0.0;
    cout << prompt;
    cin >> input;
    if (cin.fail()) {
        cout << "Please enter numbers only!\n";
        cin.clear();
        cin.ignore(1000, '\n');
        return readNumber(prompt);
    }
    return input;
}

// Main function for testing.
int main() {
    double num = readNumber("Enter a number: ");
    cout << "You entered: " << num << endl;

    return 0;
}

Exercise 15.2: Recursive Functions

In this exercise we look at several examples of recursion. Use this starter code to get started:

recfun-starter.cpp

Save the solutions in a file named recfun.cpp and turn the file in with your final project. Call all the recursive functions from main().

Recursion Problems

  1. Write a function named printDown() using recursion to print numbers from n to 0.

    Example output:

    Enter a positive number: 3
    Counting down: 3 2 1 0
    

    See Exercise: Writing a Recursive Function for more information. Call the function from main().

  2. Write a function named printUp() using recursion to print numbers from 0 to n.

    Example output:

    Counting up: 0 1 2 3
    

    Hint: Remember the discussion of pre- and post recursion. You only need to move the output statement of the previous problem to solve this one. See Exercise: Exploring Pre- and Post-Recursion for more information.

  3. Write a function using recursion named printStars() that receives a single int parameter and returns nothing. If the parameter value is greater than zero, the function prints to the console the given number of asterisks; otherwise it does nothing. For instance, calling printStars(8) displays: ******** (8 asterisks).
  4. Example output:

    Printing stars: ***
    
  5. We have a number of bunnies and each bunny has two big floppy ears. Write a non-member function named bunnyEars() that computes the total number of ears for zero or more bunnies recursively without loops, multiplication or division.

    Example results of calling the bunnyEars() function:

    bunnyEars(0) -> 0
    bunnyEars(1) -> 2
    bunnyEars(2) -> 4
    bunnyEars(3) -> 6
    
    Example output:
    Counting bunny ears: bunnyEars(3) -> 6
    

    Hint: If you know the number of ears on bunnyEars(n - 1), how many more ears are there on bunnyEars(n)? The bunnyEars() function needs to return the number of bunny ears.

  6. Write a recursive function named factorial() that computes a factorial for n, denoted mathematically by n!, where n! is the product of all positive integers less than or equal to n.

    Examples of factorials:

    factorial(0) = 1 (by definition)
    factorial(1) = 1
    factorial(2) = 2 * 1 = 2
    factorial(3) = 3 * 2 * 1 = 6
    factorial(4) = 4 * 3 * 2 * 1 = 24
    
    Example output:
    Factorial of 3: 6
    

    Hint: The function needs to return a number.

  7. Write a recursive function named sum() that totals the values between 1 and n, where n is any positive integer.

    Examples of summing:

    sum(1) = 1
    sum(2) = 2 + 1 = 3
    sum(3) = 3 + 2 + 1 = 6
    sum(4) = 4 + 3 + 2 + 1 = 10
    
    Example output:
    Summing numbers 1 to 3: 6
    

    Hint: The function needs to return a number.

  8. We want to write a function named digits() which finds the number of digits needed to represent an integer. For example, digits(1234) is 4 because 1234 has four digits (1, 2, 3, and 4). Here is a trace of the function calls:
    digits(1234)
    = digits(123) + 1
    = digits(12) + 1 + 1
    = digits(1) + 1 + 1 + 1
    = 1 + 1 + 1 + 1
    

    Compute the algorithm without loops using recursion. Call digits() with the following code in the main() function:

    // Other function calls here
    cout << "\nCounting the number of digits in an integer";
    int testValue;
    
    cout << "Please enter a number: ";
    cin >>  testValue;
    
    int numDigits = digits(testValue);
    cout << "You need " << numDigits << " digits to represent "
         << testValue << " in decimal\n";
    
    Example output:
    Please enter another number: 12345
    You need 5 digits to represent 12345 in decimal
    

    Hint: repeatedly call n / 10 until reaching n < 10.

  9. Write a function using recursion that displays a string in reverse. Do not use arrays, loops or additional strings. Example output:
    Enter a string: abcdef
    String reversed: fedcba
    

    Recall from lesson 3.2.6 that you can access part of a string using the substr() function. Also, you can determine the length of a string using the length() function. Also, you can use square bracket notation to access a single character as discussed in lesson 6.2.2.

    Also note that your recursive function will need two parameters: one for the string and one for the index of the string.

As a reward for finishing, see the Recursion Humor below.

15.2.8: Summary

  • Recursion is when an algorithm is defined in terms of itself
  • It allows us to define subproblems similar in form to the original
  • Recursion always has two parts:
    • Base case
    • A problem that is closer to the solution
  • Eventually, the base case is always called
  • Without the base case, we would have infinite recursion
  • Code executed before the cursive call is known as pre-recursion
  • Code executed after the call is known as post recursion
  • Recursion makes some code shorter and easier to understand, such as input validation

Recursion Humor

More Information on Recursion

15.3: Final Exam Preparation

Learner Outcomes

At the end of the lesson the student will be able to:

  • Discuss how to prepare for the final exam
  • Describe how to take the final exam

15.3.1: About the Final Exam

Important Final Exam Information

Published Schedule: Exam Schedule
Date and Time: Thursday, December 12 @ 1:00pm-3:50pm
Location: regular classroom, everyone at the same time

  • You must attend the exam at the scheduled time or you will receive a score of zero (0)
    • Except by prior arrangement with the instructor for unforeseeable emergency and justifiable reasons
  • Bring a valid ID to the exam
  • Be on time as you can only work on the exam during the scheduled time

15.3.2: How the Final Exam Works

  • The final exam is a Lab Practical
  • This means that you must write code for the exam
  • You will be given a series of programming problems to solve
  • Successfully completing each problem is worth some stated number of points

Administration and Ground Rules

  • I am using Canvas to administer the test
  • The exam is closed books and closed notes
  • However, you may have one 3" x 5" card of notes for the exam
  • Also, you may have blank scratch paper
  • You must use a classroom computer for taking the exam and accessing Canvas
  • You may use both Cygwin and TextPad or NotePad++ to compile and run your code
    • However, your code must compile to receive more than half-credit on the entire exam
    • Partial credit is available if you comment out your problem code
  • You may NOT use the computer to search the Internet
  • You may NOT use any electronic device during the exam except the computer in the classroom
    • Thus, you cannot use your own computer to take the exam
  • You may NOT communicate with anyone but the instructor during the exam

3"x5" Card Requirements

  • Put your name on your card
  • Maximum card or paper size is 3 inches by 5 inches
  • You may use both sides of the card
  • Notes must be handwritten and NOT photocopied
  • No more than three statements in a code sequence on the card — only snippets
  • Any 3" x 5" cards violating these rules will be confiscated before the test
  • You must turn in your 3" x 5" card after the exam

15.3.3: What the Final Exam Covers

  • The final exam is cumulative -- you should know everything we have covered
  • However, the focus is writing code for what we have learned
  • Prior exam topics are listed here:
  • See below for newer exam topics

Newer Topic Code You Must be Capable of Writing

  1. Declaring class types (9.2.2, 10.1.1)
  2. Declaring and defining member and non-member functions (9.2.4, 12.3.4)
  3. Coding constructors with and without parameters (9.2.5, 9.3.1, 9.3.2)
  4. Constructing objects and calling their functions (9.2.3, 9.3.3)
  5. Modifying (changing) values in an object (9.3.4)
  6. Writing set and get functions of classes (9.3.4)
  7. Defining and initializing vectors (10.2.2)
  8. Accessing vector elements (10.2.3)
  9. Finding and changing the size of a vector (10.2.4)
  10. Coding vector parameters and return values (10.2.5)
  11. Processing vectors using loops, including vectors of objects (10.2.4, 10.4.2)
  12. Coding common vector algorithms such as searching for, inserting and deleting elements (10.3.2, 10.3.3, 10.3.4)
  13. Opening a file stream for reading or writing (11.2.5)
  14. Reading different types of data from a file (11.2.5, 12.1.3, 12.1.4)
  15. Loading data from a file and saving it in variables, vectors and objects (11.2.5, 12.1.2-5, 12.3.5)
  16. Writing data from a vector and saving it in a file (12.1.6, 12.3.6)
  17. Developing recursive functions (15.2, Exercise 15.2)

15.3.4: Study Recommendations

  • Study over several sessions instead of one cram session
  • Review your homework assignments and solutions
  • Review the instructor's posted solutions to assignments:
    • Solutions are posted in Canvas
    • Understand how the instructor solved each problem
  • Work through the Practice Final questions in Canvas:
    • Work the problems in groups if it helps you
    • Get explanations for anything you do not understand

    Tip: Complete the entire practice exam.

Final Preparation Tips

  • Make notes on problems on the Practice Final that you had difficulty with
  • Make sure you know how to solve those types of problems
  • Review your notes and prepare your 3" x 5" card
  • Do a quick review just before bed to let your subconscious aid in long term memory.
  • Get plenty of rest before the exam

15.3.5: Exam Taking Tips

  • Arrive at the examination room a little ahead of time.
  • Listen carefully to any oral instructions for taking the exam and read instructions carefully.
  • Read every word in each test question
  • Note that you do not need to comment code for the final exam
    • Unless specifically instructed to in the exam question
  • Use the full time allowed

15.3.6: Review Materials, Questions and Answers

15.4: Sampler Demonstration

Learner Outcomes

At the end of the lesson the student will be able to:

  • Present their sampler assignment

15.4.1: Sampler Presentation

  • Here are the steps for an effective project presentation

Before the Presentation

  • Submit the following to Canvas before the presentation:
    1. README.txt file with project report
    2. All source code (i.e. .cpp files)
    3. Any other files needed to make your program function.
  • Remember that there are no late submittals accepted for the project
  • If you have problems completing the project, then turn in what you have on time and come to class
  • Bring a paper copy of your written report and give it to the instructor at the start of class
    • If you are using your paper for your presentation, be sure to bring an extra copy!
  • Also, be sure you have a quick way to access your project during class to minimize setup time
    • Flash drive (recommended in case of network problems)
    • Canvas
    • Online service

Project Setup

  • The best time to setup is before class
  • Copy your files to the instructor machine in your own folder on the Desktop
  • Verify your code compiles and your project loads its files
  • If you get stuck or do not know what to do, ask for help

During the Presentation

Present the following information:

  • Introduce yourself and state the purpose of your project
  • Compile your program completely and be sure to include all the warnings:
    g++ -Wall -Wextra -Wpedantic -o programName sourceFile.cpp
    
    • I recommend compiling with TextPad because it includes all the warnings
    • Compiling with CodeBlocks will not provide full credit unless you have a graphics project
  • Demonstrate your project, explaining aspects as you go
    • Include an explanation of all extra-credit features
    • Explain how the extra credit and interesting features work
    • Show the code for recursive functions and to help explain features
  • Limit the presentation to 5 minutes or less

After the Presentation

  • Feel free to leave (or stay) after your presentation
  • You can present to the instructor alone after the other presentations are through
  • Remember to study for the final!

End of Course Survey

Wrap Up

When class is over, please shut down your computer if it is on
Study for the final!
Last Updated: December 05 2019 @17:04:08