Ccac C++ 013 Recursion (Rq And Sum)

Front 1

In C++ a function definition may contain a call to the function being defined. In such cases the
function is said to be

Back 1

recursive

Front 2

The general outline of a
successful recursive function definition is as follows:

Back 2

■ One or more cases in which the function accomplishes its task by using one or
more recursive calls to accomplish one or more smaller versions of the task.
■ One or more cases in which the function accomplishes its task without the use of
any recursive calls. These cases without any recursive calls are called base cases or
stopping cases.

Often an if-else statement determines which of the cases will be executed. A typical
scenario is for the original function call to execute a case that includes a recursive
call. That recursive call may in turn execute a case that requires another recursive call.
For some number of times each recursive call produces another recursive call, but
eventually one of the stopping cases should apply. Every call of the function must
eventually lead to a stopping case or else the function call will never end because of an
infinite chain of recursive calls.

Front 3

To keep track of recursion (and a number of other things), most computer systems
make use of a structure called a

Back 3

stack

Front 4

a very specialized kind of memory
structure that is analogous to a ___ of paper. In this analogy there is an inexhaustible
supply of extra blank sheets of paper. To place some information in the ___, it
is written on one of these sheets of paper and placed on top of the ___ of papers.
To place more information in the ___, a clean sheet of paper is taken, the information
is written on it, and this new sheet of paper is placed on top of the ___. In this
straightforward way more and more information may be placed on the ___.
Getting information out of the stack is also accomplished by a very simple procedure.
The top sheet of paper can be read, and when it is no longer needed, it is thrown away.
There is one complication: Only the top sheet of paper is accessible. In order to read,
say, the third sheet from the top, the top two sheets must be thrown away. Since the
last sheet that is put on the stack is the first sheet taken off the stack, a stack is often
called a last-in/first-out memory structure.

Back 4

stack

Front 5

Tracing a Recursive Call

Back 5

Using a stack, the computer can easily keep track of recursion. Whenever a function
is called, a new sheet of paper is taken. The function definition is copied onto this
sheet of paper, and the arguments are plugged in for the function parameters. Then
the computer starts to execute the body of the function definition. When it encounters
a recursive call, it stops the computation it is doing on that sheet in order to compute
the value returned by the recursive call. But before computing the recursive call, it
saves enough information so that when it does finally determine the value returned by the recursive call, it can continue the stopped computation. This saved information is
written on a sheet of paper and placed on the stack. A new sheet of paper is used for the
recursive call. The computer writes a second copy of the function definition on this
new sheet of paper, plugs in the arguments for the function parameters, and starts to
execute the recursive call. When it gets to a recursive call within the recursively called
copy, it repeats the process of saving information on the stack and using a new sheet of
paper for the new recursive call.

This process continues until some recursive call to the function completes its computation
without producing any more recursive calls. When that happens, the computer
turns its attention to the top sheet of paper on the stack. This sheet contains the
partially completed computation that is waiting for the recursive computation that just
ended. Thus, it is possible to proceed with that suspended computation. When that
suspended computation ends, the computer discards that sheet of paper and the suspended
computation that is below it on the stack becomes the computation on top of
the stack. The computer turns its attention to the suspended computation that is now
on the top of the stack, and so forth. The process continues until the computation on
the bottom sheet is completed. Depending on how many recursive calls are made and
how the function definition is written, the stack may grow and shrink in any fashion.
Notice that the sheets in the stack can only be accessed in a last-in/first-out fashion, but
that is exactly what is needed to keep track of recursive calls. Each suspended version is
waiting for the completion of the version directly above it on the stack.

Front 6

a last-in/first-out memory structure. The first item referenced or removed from a it
is always the last item entered into it. It is used by computers to keep track of
recursion (and for other purposes)

Back 6

stack

Front 7

Stack Overflow

Back 7

There is always some limit to the size of the stack. If there is a long chain in which a function makes
a recursive call to itself, and that call results in another recursive call, and that call produces yet
another recursive call, and so forth, then each recursive call in this chain will cause another activation
frame to be placed on the stack. If this chain is too long, the stack will attempt to grow
beyond its limit. This is an error condition known as a stack overflow. If you receive an error message
that says “stack overflow,” it is likely that some function call has produced an excessively
long chain of recursive calls. One common cause of stack overflow is infinite recursion. If a function
is recursing infinitely, then it will eventually try to make the stack exceed any stack size limit.

Front 8

Recursion is not absolutely necessary. In fact, some programming languages do not
allow it. Any task that can be accomplished using recursion can also be done in some
other way without using recursion. For example, Display 13.2 contains a nonrecursive
version of the function given in Display 13.1. The nonrecursive version of a function
typically uses a loop (or loops) of some sort in place of recursion. For that reason, the
nonrecursive version is usually referred to as an

Back 8

iterative version

Front 9

GENERAL FORM FOR A RECURSIVE FUNCTION THAT RETURNS A
VALUE

Back 9

One or more cases in which the value returned is computed in terms of calls to the
same function (that is, using recursive calls). As was the case with void functions,
the arguments for the recursive calls should intuitively be "smaller."

One or more cases in which the value returned is computed without the use of any
recursive calls. These cases without any recursive calls are called base cases or stopping
cases (just as they were with void functions).

Front 10

If a problem can be reduced to smaller instances of the same problem, then a ___
solution is likely to be easy to find and implement.

Back 10

recursive

Front 11

A ___ algorithm for a function definition normally contains two kinds of
cases: one or more cases that include at least one recursive call and one or more
stopping cases in which the problem is solved without any recursive calls.

Back 11

recursive

Front 12

When writing a recursive function definition, always check to see that the function
will not produce ___ ___.

Back 12

infinite recursion

Front 13

When designing a ___ ___ to solve a task, it is often necessary to solve a
more general problem than the given task. This may be required to allow for the
proper recursive calls, since the smaller problems may not be exactly the same problem
as the given task. For example, in the binary search problem, the task was to
search an entire array, but the recursive solution is an algorithm to search any portion
of the array (either all of it or a part of it).

Back 13

recursive function

Front 14

When designing a recursive function, you need not trace out the entire sequence of
recursive calls for the instances of that function in your program. If the function returns a value, all you need do is check that the following three properties are
satisfied:

Back 14

1. There is no infinite recursion. (A recursive call may lead to another recursive call
and that may lead to another, and so forth, but every such chain of recursive calls
eventually reaches a stopping case.)
2. Each stopping case returns the correct value for that case.
3. For the cases that involve recursion: If all recursive calls return the correct value,
then the final value returned by the function is the correct value.

Front 15

We gave you three criteria to use in checking the correctness of a recursive function
that returns a value. Basically the same rules can be applied to a recursive void function.
If you show that your recursive void function definition satisfies the following
three criteria, then you will know that your void function performs correctly:

Back 15

1. There is no infinite recursion.
2. Each stopping case performs the correct action for that case.
3. For each of the cases that involve recursion: If all recursive calls perform their
actions correctly, then the entire case performs correctly.

Front 16

1. What is the output of the following program?
#include <iostream>
using std::cout;
void cheers(int n);
int main( )
{
cheers(3);
return 0;
}
void cheers(int n)
{
if (n == 1)
{
cout << "Hurray\n";
}
else
{
cout << "Hip ";
cheers(n - 1);
}
}

Back 16

1.
Hip Hip Hurray

Front 17

2. Write a recursive void function that has one parameter that is a positive integer and
that writes out that number of asterisks (*) to the screen, all on one line.

Back 17

2.
using std::cout;
void stars(int n)
{
cout << ’*’;
if (n > 1)
stars(n - 1);
}
The following is also correct, but is more complicated:
void stars(int n)
{
if (n <= 1)
{
cout << ’*’;
}
else
{
stars(n - 1);
cout << ’*’;
}
}

Front 18

3. Write a recursive void function that has one parameter that is a positive integer. When
called, the function writes its argument to the screen backward. That is, if the argument
is 1234, it outputs the following to the screen:
4321

Back 18

3. using std::cout;
void backward(int n)
{
if (n < 10)
{
cout << n;
}
else
{
cout << (n%10);//write last digit
backward(n/10);//write the other digits backward
}
}

Front 19

4. Write a recursive void function that takes a single int argument n and writes the integers
1, 2, . . . , n.

Back 19

4–5. The answer to 4 is writeUp;. The answer to 5 is writeDown;.
#include <iostream>
using std::cout;
using std::endl;
void writeDown(int n)
{
if (n >= 1)
{
cout << n << " "; //write while the
//recursion winds
writeDown(n - 1);
}
}
// 5
void writeUp(int n)
{
if (n >= 1)
{
writeUp(n - 1);
cout << n << " "; //write while the
//recursion unwinds
}
}

//testing code for both Exercises 4 and 5
int main( )
{
cout << "calling writeUp(" << 10 << ")\n";
writeUp(10);
cout << endl;
cout << "calling writeDown(" << 10 << ")\n";
writeDown(10);
cout << endl;
return 0;
}
/* Test results
calling writeUp(10)
1 2 3 4 5 6 7 8 9 10
calling writeDown(10)
10 9 8 7 6 5 4 3 2 1*/

Front 20

5. Write a recursive void function that takes a single int argument n and writes integers
n, n-1, . . . , 3, 2, 1. (Hint: Notice that you can get from the code for Exercise 4 to that
for this exercise, or vice versa, by an exchange of as little as two lines.)

Back 20

4–5. The answer to 4 is writeUp;. The answer to 5 is writeDown;.
#include <iostream>
using std::cout;
using std::endl;
void writeDown(int n)
{
if (n >= 1)
{
cout << n << " "; //write while the
//recursion winds
writeDown(n - 1);
}
}
// 5
void writeUp(int n)
{
if (n >= 1)
{
writeUp(n - 1);
cout << n << " "; //write while the
//recursion unwinds
}
}

//testing code for both Exercises 4 and 5
int main( )
{
cout << "calling writeUp(" << 10 << ")\n";
writeUp(10);
cout << endl;
cout << "calling writeDown(" << 10 << ")\n";
writeDown(10);
cout << endl;
return 0;
}
/* Test results
calling writeUp(10)
1 2 3 4 5 6 7 8 9 10
calling writeDown(10)
10 9 8 7 6 5 4 3 2 1*/

Front 21

6. If your program produces an error message that says “stack overflow,” what is a likely
source of the error?

Back 21

6. An error message that says “stack overflow” is telling you that the computer has
attempted to place more activation frames on the stack than are allowed on your system.
A likely cause of this error message is infinite recursion.

Front 22

7. Write an iterative version of the function cheers defined in Self-Test Exercise 1.

Back 22

7. using std::cout;
void cheers(int n)
{
while (n > 1)
{
cout << "Hip ";
n--;
}
cout << "Hurray\n";
}

Front 23

8. Write an iterative version of the function defined in Self-Test Exercise 2.

Back 23

8. using std::cout;
void stars(int n)
{
for (int count = 1; count <= n; count++)
cout << ’*’;
}

Front 24

9. Write an iterative version of the function defined in Self-Test Exercise 3.

Back 24

9. using std::cout;
void backward(int n)
{
while (n >= 10)
{
cout << (n%10);//write last digit
n = n/10;//discard the last digit
}
cout << n;
}

Front 25

10. Trace the recursive solution you made to Self-Test Exercise 4.

Back 25

10. Trace for Self-Test Exercise 4. If n = 3, the code to be executed is
if (3 >= 1)
{
writeDown(3 - 1);
}
On the next recursion, n = 2 and the code to be executed is
if (2 >= 1)
{
writeDown(2 - 1)
}
On the next recursion, n = 1 and the code to be executed is
if (1 >= 1)
{
writeDown(1 - 1)
}
On the final recursion, n = 0 and the true clause is not executed:
if (0 >= 1) // condition false
{
// this clause is skipped
}
The recursion unwinds, the cout << n << " "; line of code is executed for each
recursive call that was on the stack, with n = 3, then n = 2, and finally n = 1. The
output is 3 2 1.

Front 26

11. Trace the recursive solution you made to Self-Test Exercise 5.

Back 26

11. Trace for Self-Test Exercise 5. If n = 3, the code to be executed is
if (3 >= 1)
{
cout << 3 << " ";
writeUp(3 - 1);
}

On the next recursion, n = 2 and the code to be executed is
if (2 >= 1)
{
cout << 2 << " ";
writeUp(2 - 1);
}
On the next recursion, n = 1 and the code to be executed is
if (1 >= 1)
{
cout << 1 << " ";
writeUp(1 - 1);
}
On the final recursion, n = 0 and the code to be executed is
if (0 >= 1) // condition false, body skipped
{
// skipped
}
The recursions unwind; the output (obtained by working through the stack) is 1 2 3.

Front 27

12. What is the output of the following program?
#include <iostream>
using std::cout;
using std::endl;
int mystery(int n);
//Precondition n >= 1.
int main( )
{
cout << mystery(3) << endl;
return 0;
}
int mystery(int n)
{
if (n <= 1)
return 1;
else
return ( mystery(n - 1) + n );
}

Back 27

12. 6

Front 28

13. What is the output of the following program? What well-known mathematical function
is rose?
#include <iostream>
using std::cout;
using std::endl;
int rose(int n);
//Precondition: n >= 0.
int main( )
{
cout << rose(4) << endl;
return 0;
}
int rose(int n)
{
if (n <= 0)
return 1;
else
return ( rose(n - 1) * n );
}

Back 28

13. The output is 24. The function is the factorial function, usually written n ! and defined
as follows:
n! is equal to n*(n - 1)*(n - 2)*. . .*1

Front 29

14. Redefine the function power so that it also works for negative exponents. In order to
do this you will also have to change the type of the value returned to double. The
function declaration and header comment for the redefined version of power are as follows:
double power(int x, int n);
//Precondition: If n < 0, then x is not 0.
//Returns x to the power n.
Hint: x-n is equal to 1/( x n).

Back 29

14. //Uses iostream and cstdlib:
double power(int x, int n)
{
if (n < 0 && x == 0)
{
cout << "Illegal argument to power.\n";
exit(1);
}
if (n < 0)
return ( 1/power(x, -n));
else if (n > 0)
return ( power(x, n - 1)*x );
else // n == 0
return (1.0);
}

Front 30

15. Write a recursive function definition for the following function:
int squares(int n);
//Precondition: n >= 1
//Returns the sum of the squares of the numbers 1 through n.
For example, squares(3) returns 14 because 12 + 22 + 32 is 14.

Back 30

15. int squares(int n)
{
if (n <= 1)
return 1;
else
return ( squares(n - 1) + n*n );
}