14: Recursion and Other Topics

What We Will Cover


Continuations

Questions from last class?

Project Questions?

Final Exam Approaching

14.1: Running Under Windows

Learner Outcomes

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

  • Run console programs under Windows

14.1.1: About DLL's

  • We can run our compiled programs under Windows, on computers without Cygwin installed
  • To accomplish this, we need to include the appropriate Cygwin DLL's
  • DLL stands for Dynamic Link Library
  • A DLL is a binary file that provides a library of functions for use by Windows applications
  • All programs running under Windows use DLL's
  • Any DLL that a program uses must be available on the computer where the application is running

Cygwin DLL's

  • Cygwin provides a number of DLL's
  • These DLL's are located in the cygwin/bin directory
  • They are easy to identify because they have an extension of .dll
  • Your programs uses one or more of these DLL's when they run
  • Any DLL that your program uses must be accessible to the program
  • Thus, to run your program on a computer without Cygwin installed, we need to include a copy of the needed Cygwin DLL's

14.1.2: Finding the DLL's We Need

  • The easiest way to find the DLL's your program needs is to run the program under Windows
  • Whenever the program needs a DLL, it attempts to load the DLL
  • When it cannot load the DLL, it fails and identifies the DLL it needs

need dll message

  • To fix the problem, we copy the needed DLL into the same directory as your application
  • Since the computers in our classroom have paths set to the Cygwin\bin directory, we need to delete the path setting for this test:
    path=.

Example of Finding Needed DLL's

  • We want to run the playagain.cpp program under Windows
  • We save the program to the desktop and compile it using TextPad
  • Next we launch a Windows console:
    1. From the Start menu, Select Run...
    2. In the text box type cmd and press the Enter key
  • Then we remove the path to cygwin\bin by typing:
    path=.
  • Now when we try to run the program, we get an error message
  • We locate the Cygwin DLL we need in the cygwin\bin directory and copy it to the desktop
  • Now we can successfully run the application

Example Application

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

int main() {
    char repeat = 'y';
    while ('y' == repeat) {
        cout << "\nPlaying an exciting game!\n";
        cout << "Do you want to play again? (y/n) ";
        cin >> repeat;
    }
    cout << "\nThanks for playing!\n";

    return 0;
}

Exercise 14.1: Running on Windows without Cygwin (5m)

In this exercise we run a program under Windows without starting Cygwin or using TextPad.

Specifications

  1. Choose an application, compile it and copy the .exe file to the desktop
  2. Open a Window's terminal window:
    1. Click the Start button
    2. Select "Run..."
    3. In the Open box type in: cmd
    4. Press the Enter key
  3. Change to the Desktop directory:
    cd Desktop
    
  4. Set the path on the computer to '.':
    path=.
  5. Run the .exe file and find the missing DLL's

    To run in the Windows terminal, type the program name (no ./ needed).

  6. Copy the missing DLL's to the Desktop and run again

14.1.3: Summary

  • We can run C++ programs compiled in Cygwin on Windows computers without Cygwin installed
  • To make your programs work, we need to include any required DLL's
    • This is true for any Windows application
  • The easiest way to find the needed DLL is to run your program in the Windows terminal
  • When your program needs a DLL, Windows will try to load it
  • When Windows cannot load the DLL, it gives an error message identifying the missing DLL
  • To fix the problem, we copy the DLL into the directory in which we put your .exe file

Check Yourself

  1. What is a DLL?
  2. Why do your programs need DLL's?
  3. How can you add the DLL's needed to make your program run?

14.2: 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

14.2.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

  • When we reuse a block of code in various parts of a program, we should put the code into a function
  • 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 functions call like:
    int sum = 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

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

Activity: Write a Function Calling a Function (6m)

  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. Write a function named getName() that asks the user for a name and returns the value as a string.
  3. Call the getName() function from main() and save the returned name in a variable.
  4. Print a greeting like the following using the returned name:
    Enter your name: Puddin Tane
    Welcome, Puddin Tane!
    
    Text in red is the user input and NOT part of the program code.
  5. Save your source code file to use in the next exercise.
  6. When finished, please help those around you.

14.2.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;
    

14.2.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

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 14.2: Finishing our Function Review (5m)

In this review exercise we finish developing our functions.

  1. Start with your funreview.cpp program code from the last exercise.
  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 red 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.

14.3: 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

14.3.1: About Recursion

Recursion: when 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 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 one 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.

14.3.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 step
        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
#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) { // stopping condition
        cout << "Done washing dishes\n";
        return;
    }
    cout << count << " dishes to wash." << endl;
    wash(count - 1); // recursive step
    cout << "Washed " << count << " dishes so far." << endl;
    return; // optional for void functions
}

Try It: 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 void function named rec that has a single int parameter named 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 Try-It.
  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.

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 function calls 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?

14.3.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.

14.3.4: Pre- and Post-Recursion

  • Remember the structure of the recursive case in our dish washing example
    cout << count << " dishes to wash." << endl;
    wash(count - 1); // recursive step
    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;
    
  • Then comes the recursive call:
    wash(count - 1); // includes prerecursion: count - 1
    
  • 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
  • Notice that the calculation (count - 1) is made before the recursion (pre-recursion)

Some Recursion Terminology

Some commonly used recursion terms

Try It: Exploring Pre- and Post-Recursion (3m)

  1. Start with your code from the last Try It: Writing a Recursive Function.
  2. After the recursive call, add a print statement to display the value of num like:
    cout << num << endl;
    
  3. Compile and run your code to see the output of this post recursion statement.
  4. Save your code as an example for the next Exercise.
  5. When finished, please help those around you.
  6. Be prepared to answer the following Check Yourself questions when called upon.

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?

14.3.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 ________.

14.3.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 ________.

14.3.7: Using Recursion with Input Validation

  • Recall our discussion of input validation in lesson 6.1.7
  • We can put this input validation code inside a function as shown below:

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 occurs 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 14.3: Recursion 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 project. Call all the recursive functions from main().

Recursive 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 Try It: 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 Try It: 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. It 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.

14.3.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

Wrap Up

Due Next:
Sampler Project (12/7/17)
When class is over, please shut down your computer if it is on
Work on your project!
Last Updated: December 07 2017 @16:25:13