C++ lecture 12
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (223.09 KB, 19 trang )
C++ Programming
Lecture 12
Functions – Part IV
The Hashemite University
Computer Engineering Department
Adapted from the textbook slides
Outline
Introduction.
Recursion.
Reference parameters and
variables.
Functions call by reference and call
by value.
Examples.
The Hashemite University
2
Recursion I
Recursive functions
Are functions that calls themselves.
Recursive functions know the solution for the simplest case
called base case.
If the function is called with the base case the function
returns a result
else, 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 (recursive calls)
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.
The recursion step executes while the original call to
the function is still open (not finished yet).
The Hashemite University
3
Recursion II
Example: factorial
n! = n * ( n – 1 ) * ( n – 2 ) * … * 1
Can be solved either iteratively or recursively:
Iteratively:
int factorial = 1;
for (int count = n; count >= 1; count--)
factorial *= count;
int fact (int number)
Recursively:
Recursive relationship ( n! = n * ( n – 1 )! )
5!
4!
3!
2!
1!
=
=
=
=
=
5
4
3
2
1
*
*
*
*
4!
3!
2!
1!
{
If ( number<=1)
return 1;
else
Base case (1! = 0! = 1)
return number * fact (number1);
}
The Hashemite University
4
Example Using Recursion:
The Fibonacci Series
Fibonacci series: 0, 1, 1, 2, 3, 5, 8...
Each number sum of two previous ones
Example of a recursive formula:
fib(n) = fib(n-1) + fib(n-2)
// for n>=2 (not base case)
C++ code for fibonacci function
long fibonacci( long n )
{
if ( n == 0 || n == 1 ) // base case
return n;
else return fibonacci( n - 1 ) + fibonacci( n – 2 );
}
The Hashemite University
5
Example Using Recursion:
The Fibonacci Series
Diagram of Fibonacci function
f( 3 )
return
return
f( 1 )
return 1
+
f( 2 )
+
f( 1 )
f( 0 )
return 1
return 0
The Hashemite University
6
1
// Fig. 3.15: fig03_15.cpp
2
// Recursive fibonacci function
3
#include <iostream>
4
5
using std::cout;
6
using std::cin;
7
using std::endl;
8
9
unsigned long fibonacci( unsigned long );
10
11 int main()
12 {
13
unsigned long result, number;
14
15
cout << "Enter an integer: ";
16
cin >> number;
17
result = fibonacci( number );
18
cout << "Fibonacci(" << number << ") = " << result << endl;
19
return 0;
1. Function prototype
20 }
21
22 // Recursive definition of function fibonacci
Only the base cases return values.
1.1 Initialize variables
All other cases call the fibonacci
23 unsigned long fibonacci( unsigned long n )
24 {
25
26
27
28
29 }
if ( n == 0 || n == 1 )
// base case
function again.
return n;
else
// recursive case
2. Input an integer
return fibonacci( n - 1 ) + fibonacci( n - 2 );
Enter an integer: 0
Fibonacci(0) = 0
Enter an integer: 1
Fibonacci(1) = 1
Enter an integer: 2
Fibonacci(2) = 1
Enter an integer: 3
Fibonacci(3) = 2
Enter an integer: 4
Fibonacci(4) = 3
Enter an integer: 5
Fibonacci(5) = 5
Enter an integer: 10
Fibonacci(10) = 55
Enter an integer: 6
Fibonacci(6) = 8
Enter an integer: 20
Fibonacci(20) = 6765
Enter an integer: 30
Fibonacci(30) = 832040
Enter an integer: 35
Fibonacci(35) = 9227465
Program Output
Recursion vs. Iteration
Repetition
Iteration: explicit loop (repetition structure)
Recursion: repeated function calls (selection structure)
Termination
Iteration: loop condition fails
Recursion: base case recognized
Both can have infinite loops (how ?)
Each recursive call saves the current function state and creates
another copy of the recursive function with another values
Balance between performance (iteration) and good
software engineering (recursion).
The Hashemite University
9
Recursion example
#include<iostream>
using namespace std;
int rec_fun(int y); // function prototype
int main()
{
cout<
}
int rec_fun(int y)
{
if(y>10) // this is the base case
return y+1;
else
return y- rec_fun(y*2);
}
Recursive calls
The Hashemite University
10
Reference Variables I
Reference variable is an alias to some variable.
& (ampersand) is used to signify a reference
E.g:
int x = 0;
int &y = x; //y is a reference to an integer which is x
Here y is an alias to the variable x since the
address of y is equal to the address of x.
So, modifying either x or y both variables will
have the same modified value since both of them
refer to the same memory location or address.
The Hashemite University
11
Reference Variables II
Reference variables must be initialized within
the same statement that defines them, if not it
will be a syntax error (reference must be
initialized).
Reference variables must be initialized with a
variable only, constants and expressions are
not allowed syntax error.
You cannot reassign the reference variable to
another variable since you simply copy the
value of the new variable in the old one and
you still working on the old one and this is
considered as a logical
error.
The Hashemite
University
12
Call By Reference I
Two types of function call:
Call by value
Copy of data passed to function.
Changes to copy do not change the original
found in the caller.
Used to prevent unwanted side effects.
Call by reference
Function can directly access data.
Changes affect the original found in the caller.
No copy exist (reduce overhead), however, it is
dangerous since the original value is
overwritten.
The Hashemite University
13
Call By Reference II
Function arguments can be passed by
reference.
In both the function header and prototype
you must proceed the reference variable
by &.
In the function call just type the name of
the variable that you want to pass.
Inside the function body use the
reference variable by its name without &.
The Hashemite University
14
Call By Reference III
Again the reference argument must be
a variable (constants or expressions are
not allowed syntax error
E.g.:
void change( int &variable )
{ variable += 3; }
Adds 3 to the input variable which also
affects the original variable (passed as
argument to function change in the caller).
The Hashemite University
15
Call By Reference IV
Note that till now we have talked about the
function arguments or parameters to be
reference variables. But what about the return
result? Can we make it a reference variable?
If the function return a reference variable this means
that it returns an alias to a variable inside that function.
If this variable is not static (i.e. automatic) then this
variable will be destroyed when the function ends.
So, this function will return a reference to an undefined
variable which is called dangling reference.
Such thing is considered as a logical error.
As possible avoid the usage of reference return results
even to static variables.
The Hashemite University
16
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
// Fig. 3.20: fig03_20.cpp
// Comparing call-by-value and call-by-reference
// with references.
#include <iostream>
using std::cout;
using std::endl;
Notice the use of the & operator
int squareByValue( int );
void squareByReference( int & );
int main()
{
int x = 2, z = 4;
cout <<
<<
<<
<<
"x = " << x << " before squareByValue\n"
"Value returned by squareByValue: "
squareByValue( x ) << endl
"x = " << x << " after squareByValue\n" << endl;
cout << "z = " << z << " before squareByReference" << endl;
squareByReference( z );
cout << "z = " << z << " after squareByReference" << endl;
return 0;
}
int squareByValue( int a )
{
return a *= a;
// caller's argument
notHashemite
modified University
The
}
17
32
33 void squareByReference( int &cRef )
34 {
35
cRef *= cRef;
// caller's argument modified
36 }
x = 2 before squareByValue
Value returned by squareByValue: 4
x = 2 after squareByValue
z = 4 before squareByReference
z = 16 after squareByReference
The Hashemite University
18
Additional Notes
This lecture covers the following
material from the textbook:
Fourth Edition
Chapter 3: Sections 3.12, 3.13, 3.14, 3.17
The Hashemite University
19
