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

In this review exercise we finish developing our functions.

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

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

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 the base: 2
Enter the exponent: 3
2^3 = 8

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

Once you finish, check your source code by clicking here.

#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);
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) {
int result = 1;
for (int i = 0; i < y; i++) {
result = result * x;
}
return result;
}

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

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

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 function named rec with the following prototype:

void rec(int 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 by clicking here.

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
}

Save your code for the next Exercise.

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.

Once you finish, check your source code by clicking here.

#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():

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.

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

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:

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.

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:

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.