1

Chapter 3 - Functions
Outline
3.12 Recursion
3.13 Example Using Recursion:
3.14 Recursion vs. Iteration
3.15 Functions with Empty Parameter Lists

 2000 Prentice Hall, Inc. All rights reserved.

 2

3.12 Recursion
• Recursive functions
– Are functions that call themselves
– Can only solve a base case
– If not base case, the function breaks the problem into a
slightly smaller, slightly simpler, problem that resembles the
original problem and
• Launches a new copy of itself to work on the smaller problem,
slowly converging towards the base case
• Makes a call to itself inside the return statement
– Eventually the base case gets solved and then that value
works its way back up to solve the whole problem

 2000 Prentice Hall, Inc. All rights reserved.

 3

3.12 Recursion
• Example: factorial
n! = n * ( n – 1 ) * ( n – 2 ) * … * 1
5!=5*4*3*2*1=120
– Recursive relationship ( n! = n * ( n – 1 )! )
5! = 5 * 4!
4! = 4 * 3!…
– Base case (1! = 0! = 1)

 2000 Prentice Hall, Inc. All rights reserved.

 Recursion

void print(int n)
{
if (n<1) return;
cout<<n;
print(n-1);
}

What would be the output of print(5)?

 2000 Prentice Hall, Inc. All rights reserved.
 Recursion unrolled
What would be the output of print(5)?
print(5)
5 <1 ?
cout<<n;  5
print(4)
4 <1 ?
cout<<n;  4
print(3)
3 <1 ?
cout<<n;  3
print(2)
2<1 ?
cout<<n;  2
print(1)
1 <1 ?
cout<<n;  1
print(0)
0<1 0
return;

 2000 Prentice Hall, Inc. All rights reserved.

 Recursion

void print(int n)
{
if (n<1) return;
print(n-1);
cout<<n;
}

What would be the output of print(5)?

 2000 Prentice Hall, Inc. All rights reserved.

 void print(int n){

Recursion unrolled if (n<1) return;

print(n-1);

What would be the output of print(5)? }

cout<<n;

print(5)
5 <1 ?
print(4)
(4 <1) ?
print(3)
(3 <1) ?
print(2)
(2<1) ?
print(1)
(1 <1) ?
print(0)
0
(0 < 1) return
cout<<n;  1
cout<<n;  2
cout<<n;  3
cout<<n;  4
cout<<n;  5

 2000 Prentice Hall, Inc. All rights reserved.

 Recursion
void print(int n)
{
if (n<1) {}
else
cout<<n;
print(n-1);
}

What would be the output of print(5)?

 2000 Prentice Hall, Inc. All rights reserved.
 9

3.14 Recursion vs. Iteration

• Repetition
– Iteration: explicit loop
– Recursion: repeated function calls
• Termination
– Iteration: loop condition fails
– Recursion: base case recognized
• Both can have infinite loops
• Balance between performance (iteration) and good
software engineering (recursion)

 2000 Prentice Hall, Inc. All rights reserved.

 10
3.15 Functions with Empty Parameter
Lists
• Empty parameter lists
– Either writing void or leaving a parameter list empty
indicates that the function takes no arguments
void print();
or
void print( void );
– Function print takes no arguments and returns no value

 2000 Prentice Hall, Inc. All rights reserved.

 // Functions that take no arguments 11
Outline
#include <iostream.h> Notice the two ways of
void function1(); declaring no 1. Function
void function2( void ); arguments. prototypes (take
int main() no arguments)
{
2. Call the
function1();
functions
function2();
return 0; 3. Function
} definitions

void function1()
{
cout << "function1 takes no arguments" << endl;
}

void function2( void )

{
cout << "function2 also takes no arguments" << endl;
}
function1 takes no arguments
function2 also takes no arguments Program Output
 2000 Prentice Hall, Inc. All rights reserved.
 12

3.20 Function Overloading

• Function overloading
– Having functions with same name and different parameters
– Should perform similar tasks ( i.e., a function to square
ints, and function to square floats).
int square( int x) {return x * x;}
float square(float x) { return x * x; }
==============================
int sum(int x, int y, intz)
float sum(float x, float y)

– Program chooses function by signature

• signature determined by function name and parameter types
– Can have the same return types

 2000 Prentice Hall, Inc. All rights reserved.

1 // Fig. 3.25: fig03_25.cpp 13
2 // Using overloaded functions Outline
3 #include <iostream>
4 Functions have same name but
different parameters 1. Define
5 using std::cout;
overloaded function
6 using std::endl;
7
8 int square( int x ) { return x * x; } 2. Call function
9
10 double square( double y ) { return y * y; }
11
12 int main()
13 {
14 cout << "The square of integer 7 is " << square( 7 )
15 << "\nThe square of double 7.5 is " << square( 7.5 )
16 << endl;
17
18 return 0;
19 }

The square of integer 7 is 49 Program Output

The square of double 7.5 is 56.25

 2000 Prentice Hall, Inc. All rights reserved.

 14
3.19 Unary Scope Resolution
Operator
• Unary scope resolution operator (::)
– Access global variables if a local variable has same name
– not needed if names are different
– instead of variable use ::variable

 2000 Prentice Hall, Inc. All rights reserved.

 15
// Fig. 3.24: fig03_24.cpp Outline
// Using the unary scope resolution operator
1. Define variables
#include <iostream.h>

#include <iomanip.h> 2. Print variables

const double PI = 3.14159265358979;

Notice the use of ::
int main()
{
const float PI = static_cast< float >( ::PI );
cout << setprecision( 20 )

cout << ::PI << endl;

return 0;
}

Program Output
Local float value of PI = 3.141592741012573242
Global double value of PI = 3.141592653589790007

 2000 Prentice Hall, Inc. All rights reserved.