14: Recursion and Other Topics

Quick Index

Instructor's Page

Home
Canvas
CodeLab

Schedule
Syllabus
Room Policies

Help
FAQ's
How To's
Links

Español
Chinese
Japanese

14: Recursion and Other Topics
What We Will Cover

Reminders:

Please silence all cell phones and other noise makers

Sit at a computer station, start your computer and login

When class is over, please shut down your computer.

Remember that you lose any files not saved.

Continuations

14.1: Reviewing Functions

14.1.1: Defining and Calling Functions

14.1.2: Parameters and Scope

14.1.3: Prototypes, Terminology and Style

Exercise 14.1: Finishing our Function Review

14.2: Introduction to Recursion

14.2.1: About Recursion

14.2.2: Implementing Recursive Functions

14.2.3: How Recursion Works

14.2.4: Pre- and Post-Recursion

14.2.5: Developing a Recursive Algorithm

14.2.6: Coding the Recursive Algorithm

14.2.7: Using Recursion with Input Validation

Exercise 14.2: Recursion Functions

14.2.8: Summary

14.3: Project Design Review

Exercise 14.3: Review your design with a peer

Wrap Up

Due last Sunday: A12-Storing Information (11/25/18)
Due Today: A13-Project Design and Prototype (11/28/18)
Due Next: A14-Sampler Project (12/5/18)

Continuations

Feedback on A11 - Keeping Lists

Formatting is important... though I was pretty unclear these last two assignmnets... no deductions for price/per vote display. New lines and column lineup and cents were obvious.
comment your code! Details matter industry!

Questions from last class?

Project Questions?

A14-Sampler Project (12/5/18)

Final Exam Approaching

Final Examinations Schedule

Note: If you need the proctoring center, schedule it two weeks early

^ top

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

^ top

14.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
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
The following code snippet displays the value ________.
int fun() {
    return 12;
}
// other code here
cout << fun();
Which of the following is a function definition and which is a function call?

add(32, 10);

int add(int a, int b) { /* statements */ }
The result of compiling and running the following code snippet is ________.
void fun() {
    return 12;
}
// main code here
cout << fun();
Does not compile

Compiles but does not run

Displays 12 to the terminal window

Displays void to the terminal window
The best return type for a function with the following return statement is ________.
return "42.3";
Activity: Write a Function Calling a Function (6m)
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;
}
Write a function named getName() that asks the user for a name and returns the value as a string.

Call the getName() function from main() and save the returned name in a variable.
Print a greeting like the following using the returned name:
Enter your name: Puddin Tane
Welcome, Puddin Tane!
Text in aqua is the user input and NOT part of the program code.
Save your source code file to use in the next exercise.

When finished, please help those around you.
^ top

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

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:

Call-by-value: a copy of the argument's value is passed

Call-by-reference: the address of the argument variable is passed

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
The following code displays the value ________.
int fun(int param) {
    param = 45;
    return param - 3;
}
// main code here
int x = 7;
cout << fun(x);
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;
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;
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;
^ top

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

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

^ top

Exercise 14.1: Finishing our Function Review (5m)

In this review exercise we finish developing our functions.
Start with your funreview.cpp program code from the last exercise.
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);
Write the definition (implementation) of the above function after main().
Hint: use a loop for the calculation.

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

Test your code with values like those shown below.

Save your source code file to submit as part of the sampler project.

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 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.
#include <iostream>
using namespace std;

/**
    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);

string getName() {
    cout << "Enter your name: ";
    string name;
    getline(cin, name);
    return name;
}

int main() {
    string name = getName();
    cout << "Welcome, " << name << endl;
    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) {
    int result = 1;
    for (int i = 0; i < y; i++) {
        result = result * x;
    }
    return result;
}
^ top

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

^ top

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

14.2.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, leave room

Else:

wash a dish

Ask someone else to wash the dishes

leave room

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

True or false: a recursive step needs to solve some part of a problem.

The easy-to-solve part of a recursion is know as the ________ case.

True or false: every recursive algorithm must have a base case.

^ top

14.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 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)
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;
}
Add a stub for a void function named rec that has a single int parameter named num.
Within main() add the following code to call the rec() function:
int num;
cout << "What number to count from? ";
cin >> num;
rec(num);
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.

Save your code for the next Try-It.

Check to see if the student on either side of you needs help. If so, offer to help them.

Be prepared to answer the following questions.
Check Yourself

True or false: Recursion is a form of looping but without using a loop statement.

Recursion is implemented in C++ using function calls and ________.

In recursive algorithms, an if-statement is needed to test for the ________ case.

What are the elements of using recursion to loop?

^ top

14.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:

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)

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

Check Yourself

Items are placed on the top of a stack and removed from the ________.

True or false: the last item placed on a stack is the first item removed.

Functions are tracked on a call stack with a stack ________.

True or false: a function on a call stack is active and has yet to complete execution.

^ top

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

Try It: Exploring Pre- and Post-Recursion (3m)
Start with your code from the last Try It: Writing a Recursive Function.
After the recursive call, add a print statement to display the value of num like:
cout << num << endl;
Compile and run your code to see the output of this post recursion statement.

Save your code as an example for the next Exercise.

When finished, please help those around you.

Be prepared to answer the following Check Yourself questions when called upon.
Check Yourself
True or false: within the recursive step, code executed before the recursive call is known as pre-recursion.

Within the recursive step, code executed after the recursive call is known as ________ recursion.
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;
}
In the above recursive code, the post-recursion statement is ________.
What is the effect of pre-recursion vs. post-recursion?
^ top

14.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:

Use a solution to a smaller or easier version of a problem to arrive at the solution itself

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:
x^y
A function prototype for exponentiation could be:
int power(int x, int y);
The definition of exponentiation when y is a positive integer is:
x^y = 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
x^y = x * x^{y - 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 x^{y - 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 x⁰, which is 1

Else (while y ≥ 1):

Ask someone else to compute x^{y - 1}

We multiply the result of x^{y - 1} times x

Activity: Calculating 2^x

For this activity we will calculate 2^x using the power of student brains.

You will be asked for the answer to 2^x, where x is an integer value.

If the value of x is one or less then say the answer.
For example, say: "2¹ is 2."

Otherwise, ask the student next to you for the value of 2^{x - 1}
For example, if you were asked for 2¹⁴ , ask the student next to you: "What is 2¹³?"

When you get an answer to your question, double it and say the answer out loud.
For example, if you get an answer to 2¹³, say: "2¹⁴ is 16,384."

Check Yourself

True or false: exponentiation with positive integers corresponds to repeated multiplication.

The following is known as a ________ relation.
x^y = x * x^{y - 1}

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

^ top

14.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?
Note how the power() function calls itself
int power(int x, int y) {
    ...
        y = y - 1;
        int result = power(x, y);
        result = result * x;
    ...
}
Calling a function from within that function is a recursive call

The arguments to the recursive call must define a task that is easier, smaller or closer to completion than the original task

In this case, the caller must calculate x^y

But the recursive call is an easier task: x^{y - 1}
Which line(s) of code is the base case?
The power() function has a conditional return that does not involve a recursive call known as the base case:
int power(int x, int y) {
    if (y == 0) {
        return 1;
    ...
    }
}
The termination step is essential to any recursive procedure

It checks to see if the task can be carried out without using recursion

If so, it terminates the recursion by preventing any further recursive calls

Note that the terminating condition must be checked before a recursive call

Otherwise, the recursive call would go on indefinitely

The terminating condition would never be reached
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
When a recursive function calls itself, that step known as the ________ step.

True or false: the base case always includes a recursive function call.

True or false: the recursive step must always define a task that is easier, smaller or closer to completion than the original task.
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;
    }
}
In the above recursive code, the post-recursion calculation is ________.
^ top

14.2.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;
}
^ top

Exercise 14.2: Recursion Functions (20m)

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
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().
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.
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).

Example output:
Printing stars: ***
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.
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.
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.
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.
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.

^ top

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

If you still don't get it, See: "Recursion".

"To understand recursion, you must first understand recursion." ~unknown

Search Google about recursion

Hulk Hogan Recursively

Source: http://boingboing.net/2011/11/16/hulk-hogan-recurssion.html
Even more recursive example: Hogan recursion animation

More Information on Recursion

Recursion: from Wikipedia

Recursion: from Harvard CS50.tv

^ top

14.3: Project Design Review

Learner Outcomes

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

Review feedback on your project

Practice describing your project

Exercise 14.3: Review your design with a peer (15m)

Take out a piece of paper and answer these questions

Name of your project

purpose of your project - what's it do, what problem does it solve

inputs - from where... keyboard/file?

outputs - to where... console/file?

names of your class(es)

READOUT

Round the room - each of you will take a few minutes and share:

Name of your project

purpose of your project - what's it do, what problem does it solve

inputs - from where... keyboard/file?

outputs - to where... console/file?

names of your class(es)

^ top

TURN-IN for 5 points

Put your name on the paper, indicate who you reviewed it with. TURN IN to instructor before you leave class

Wrap Up

Due Next:
Due last Sunday A12-Storing Information (11/25/18)
Due Today: A13-Project Design and Prototype (11/28/18)
Due Next: A14-Sampler Project (12/5/18)

When class is over, please shut down your classroom computer.
Work on your project!
^ top

Home | Canvas | Eve Schedule
Syllabus | Help | FAQ's | HowTo's | Links

Last Updated: Wed Nov 28 10:12:22 PST 2018

What We Will Cover

Continuations

Feedback on A11 - Keeping Lists

Questions from last class?

Project Questions?

Final Exam Approaching

14.1: Reviewing Functions

Learner Outcomes

14.1.1: Defining and Calling Functions

Defining Functions

Function Calls

Check Yourself

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

14.1.2: Parameters and Scope

Local and Global Variables

Check Yourself

14.1.3: Prototypes, Terminology and Style

Some Function Terminology

Function Style

Exercise 14.1: Finishing our Function Review (5m)

14.2: Introduction to Recursion

Learner Outcomes

14.2.1: About Recursion

Recursion Example: Many Hands Make Light Work

Algorithm For Washing Dishes

Recursive Elements

Check Yourself

14.2.2: Implementing Recursive Functions

Implementation of Recursive Example

Try It: Writing a Recursive Function (5m)

Check Yourself

14.2.3: How Recursion Works

Function Call Stack

Call Stack for wash(3)

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

Check Yourself

14.2.4: Pre- and Post-Recursion

Some Recursion Terminology

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

Check Yourself

14.2.5: Developing a Recursive Algorithm

Thinking Recursively

Recursive Algorithm For Exponentiation

Activity: Calculating 2x

Check Yourself

14.2.6: Coding the Recursive Algorithm

Example Code

Tracing the Structure

Tracing the Execution

Instrumented Source Code

Check Yourself

14.2.7: Using Recursion with Input Validation

Example of Input Validation Function with Loop

Example of Input Validation with Recursion

Exercise 14.2: Recursion Functions (20m)

Recursive Problems

14.2.8: Summary

Recursion Humor

More Information on Recursion

14.3: Project Design Review

Learner Outcomes

Exercise 14.3: Review your design with a peer (15m)

READOUT

TURN-IN for 5 points

Wrap Up

Call Stack for `wash(3)`

Activity: Calculating 2^x