Chapter One

Functions

1
Objectives
At the end of this chapter, students will be able to
Identify the basic concepts of a function in C++
Use predefined functions in C++
Identify the syntax for declaring and defining functions in C++
Identify components of a user defined function in C++
Differentiate predefined and user defined functions
Differentiate parameters and arguments of a function
Identify usage of default arguments
Identify function overload in C++
identify static and auto variables (global and local variables)
Differentiate pass by value and pass by reference while calling /invoking functions
Get introduced to recursive functions
Demonstrate usage of functions to systematically solve a complex problem by breaking it down
into manageable tasks using C++ functions

Chapter_One_Functions
2
C++ Functions
● A way to write a program is to first design the method the program use, and
write this method in English – this is what we call algorithm.
● A good plan of attack for designing the algorithm is to break down the task
to be accomplished into a few subtask, decompose subtasks into smaller
subtasks, and so forth.
● This is top-down design or divide and conquer
● Preserving top-down structure
○ Makes the program easier to understand, easier to change if need be, and
○ Easier to write, test, debug
● C++ provide facilities to include separate subparts inside of a program, called
functions
● In other programming languages, the subprograms are known as procedures,
or methods
● A function can be defined, either as part of the main program or in a separate
file so that it can be use by several programs

Chapter_One_Functions
3
C++ Functions…Hierarchical
boss-function/worker-function
relationship

Chapter_One_Functions
4
C++ Functions…Hierarchical
boss-function/worker-function relationship…
● A boss (similar to the calling function) asks a worker (similar to a
called function) to perform a task and report back (i.e., return) the
results after completing the task.
● The boss function does not know how the worker function performs its
designated tasks.
● The worker may also call other worker functions, unbeknownst to the
boss.
● This hiding of implementation details promotes good software engineering.
● Depiction (previous slide) shows the boss function communicating
with several worker functions.
● The boss function divides the responsibilities among the worker
functions, and worker1 acts as a “boss function” to worker4 and
worker5.
● The relationship does not need to be hierarchical, but often it is, which
makes it easier to test, debug, update and maintain programs
Chapter_One_Functions
5
Function
● A function is a construct for grouping statements together to perform a task.
● A function provides a convenient way of packaging a computational way, so
that it can be used as often as required.

● Therefore, a function is a block of code designed to tackle a specific problem

(task). Eg. withdrawal, deposit, loan, sum, product, etc in an account
management system
Function Basics

● One of the best ways to tackle a problem is to start with the overall goal, then
divide this goal into several smaller tasks. You should never lose sight of the
overall goal, but think also of how individual pieces can fit together to
accomplish such a goal.

● If your program does a lot, break it into several functions. Each function
should do only one primary task.

Chapter_One_Functions
6
 Function cont’d
• Functions allow you to modularize a program by separating
its tasks into self-contained units.
• You’ve used a combination of library functions and your
own functions in almost every program you’ve written.
• There are several motivations for modularizing a program
with functions:
• Software reuse. we do not have to define how to read a line of text from
the keyboard—C++ provides this capability via the getline function of the
<string> header.
• Avoiding code repetition.
• Dividing a program into meaningful functions makes the program easier to
test, debug and maintain.
• To promote software reusability, every function should be
limited to performing a single, well-defined task, and the
name of the function should express that task effectively.
Chapter_One_Functions
7
 Function cont’d
C++ functions generally adhere to the following rules.
● Every function must have a name
● Function names are made up and assigned by the programmer following the
same rules that apply to naming variables
● They must be valid identifiers whose size vary per compilers
● All function names have one set of parenthesis immediately following them
● This helps you (and C++ compiler) differentiate them from variables
● The body of each function, starting immediately after parenthesis of the
function name, must be enclosed by a pair of braces
● Functions can be predefined or user defined
● Predefined functions require inclusion of header files which contain their
definition
● the main(), function is not a member of a class; it is called global function

Chapter_One_Functions
8
 Predefined functions
• C++ comes with libraries of predefined functions that you can use in your
programs. Example:
• sqrt function is a predefined function calculates the square root of
a positive real number
• You can use a function call directly in a cout statement, as in the
following:
cout << "The side of a square with area " << area
<< " is " << sqrt(area); or
cout<<sqrt(9); // which produces 3
sqrt() is defined in the header file cmath, thus we need to include it:
#include <cmath>
• A few predefined functions are shown (next slide);
• Notice that the absolute value functions abs and labs are in the library with
header file cstdlib, while fabs is defined in cmath
• so any program that uses any of these functions must include the
appropriate directive:
#include <cstdlib> or #include <cmath>
• Next slide shows sample of predefined functions along with library headers
Chapter_One_Functions
9
Chapter_One_Functions 1
0
Chapter_One_Functions 1
1
Random number generator
• Games and simulation programs often require the generation of
random numbers.
• C++ has a predefined function to generate pseudorandom numbers.
• A pseudorandom number is one that appears to be random but is
really determined by a predictable formula.
• For example, here is the formula for a very simple pseudorandom
number generator that specifies the ith random number Ri based
on the previously generated random number Ri-1:
Ri = (Ri−1 x 7) % 11
• Let’s set the initial “seed,” R0 = 1. The first time we fetch a “random”
number
• we compute R1 with the formula:
R1 = (R0 x 7) % 11 = (1 x 7) % 11 = 7 % 11 = 7
• The second time we fetch a “random” number we compute R2 with:
R2 = (R1 x 7) % 11 = (7 x7) % 11 = 49 % 11 = 5
• The third time we fetch a “random” number we compute R3 with:
R3 = (R2 x 7) % 11 = (5 x 7) % 11 = 35 % 11 = 2
• and so on.
Chapter_One_Functions 1
2
Random number generator
• C++ has a predefined function called rand(), defined in cstdlib header
generates random rather pseudorandom numbers between 0 and
RAND_MAX (inclusive)
• Every time the calling program is run, the same number is displayed; this is because
srand(1) is used by default
• To seed C++’s random number generator use the
predefined method srand
• srand returns no value and takes as input an unsigned
integer that is the initial seed value
• To always seed the random number generator with the value 5, we
would use: srand(5); such fixed seed makes the rand() function
pseudorandom
• Take away question: what does a die roll show up with the
following statement?
• int die = rand()%6 +1;
• How do you make the die show up more random?
Chapter_One_Functions 1
3
Predefined functions…
• To vary the random number sequence every time the
program is executed, we can seed the random number
generator with the time of day:
• Call srand(time(0)); before rand() is called
• Invoking the predefined function time(0) returns the number
of seconds that have elapsed since January 1, 1970 on
most systems. The time function requires you to include the
ctime library.
#include <cstdlib>
#include <ctime>
...
srand(time(0));
//Calling rand() seems more random
int die = rand()%6 +1; // die holds an integer: 1 to 6
•

Chapter_One_Functions 1
4
Predefined functions…
• To vary the random number sequence every time the
program is executed, we can seed the random number
generator with the time of day:
• Call srand(time(0)); before rand() is called
• Invoking the predefined function time(0) returns the number
of seconds that have elapsed since January 1, 1970 on
most systems. The time function requires you to include the
ctime library.
#include <cstdlib>
#include <ctime>
...
srand(time(0));
//Calling rand() seems more random
int die = rand()%6 +1; // die holds an integer: 1 to 6

Chapter_One_Functions 1
5
Predefined functions: takeaway questions
1. Explore the usage of predefined functions along with
the required header file, arguments and value returned
i. floor() and ceil()
ii. round() and trunc()
iii. abs() and fabs()
iv. rand() and srand()
v. sqrt() and pow()
2. Write a simple program that displays a random
sequence of integers that are a representation of a
face on a fair die (simulate rolling a six sided die)
i. with time(0) as an argument to srand()
ii. With 35 as an argument to srand()
3. Write a C++ statement that displays the number of
seconds elapsed since January 1, 1970
Chapter_One_Functions 1
6
Predefined functions: takeaway questions …
1. Write a C++ statement that displays the upper
limit of the range of numbers that rand() can
produce
2. Suppose you have: int totalCandy = 15,
numberOfPeople = 2; double candyPerPerson;
Identify the difference between
i. candyPerPerson = static_cast<double>(totalCandy)/numberOfPeople; and
ii. candyPerPerson = static_cast<double>(totalCandy/numberOfPeople);
3. Write a single statement that prints a number at
random from each of the following sets:
i. 0, 3, 6, 9, 12
ii. 3, 5, 7, 9, 11, 13
iii. 6, 10, 14, 18
Chapter_One_Functions 1
7
User defined functions
Declaring, defining and calling functions
Declaring function (also called function prototype)
● It is an interface that specifies how a function may be used.
● A function declaration tells you all you need to know to write a call to the
function. A function declaration is required to appear in your code prior to a
call to a function whose definition has not yet appeared. Function
declarations are normally placed before the main part of your program.
● It consists of three entities:
● The function return type. This specifies the type of value the function
returns. Eg. int, char, double, etc
● A function which returns nothing should have a return type void.
● The function name. this is simply a unique identifier
• The function parameters (also called its signature). This is a set of zero or more typed
identifiers used for passing values to the function
• Eg. int withdrawal(float amt);

Chapter_One_Functions 1
8
 Declaring a Function-Prototype
• A function prototype is a declaration of a function that tells the compiler
the function’s name, its return type and the types of its parameters.
• The portion of a function prototype that includes the name of the function
and the types of its arguments is called the function signature or simply
the signature.
• function signature is crucial for function overloading
• function prototype is the same as the first line of the corresponding
function definition, but ends with a required semicolon.
• Parameter names in function prototypes are optional (they’re ignored by
the compiler)
•Example: int maximum(int x, int y, int z); // function prototype
• This is a function prototype, which describes the maximum function without revealing its
implementation.
• Declaring function parameters of the same type as int x, y instead of int x,
int y is a syntax error— a type is required for each parameter in the
parameter list

Chapter_One_Functions 1
9
Uses of function Prototype
• The compiler uses the prototype to
• Ensure the header of the prototype matches with that in its
definition
• Check the call to the function contains the correct number,
sequence and types of arguments
• Ensure that the value returned by the function can be used
correctly in the expression that called the function
• Ensure that each argument is consistent with the type of the
corresponding parameter—for example, a parameter of type
double can receive values like 7.33, 22 or–0.03456, but not
a string like "hello“
• If the arguments passed to a function do not match the
types specified in the function’s prototype, the compiler
attempts to convert Chapter_One_Functions
the arguments to those types, and what
2
happens if the conversion is not allowed? 0
Syntax for function declaration and definition

Chapter_One_Functions 2
1
 Functions definition
• To be used in a program, a function must be defined
first and then called
• A function definition has everything a function
declaration has, plus the body of a function
• A function definition describes how the function
computes the value it returns or how it manipulates data
• function definition consists of two parts: Function header
and function body
• Function body is the block that contains the
computational steps implementing the logic of the
function, enclosed in a pair of braces
• The scope of a function is the region is of a program in
which the function is known and is accessible
Chapter_One_Functions 2
2
Calling a function
● Using a function involves ‘calling’ it.
● Calling a function means making the instruction of the function to be executed
● A function call consists of the function name followed by the call operator
brackets ‘()’, inside which zero or more comma-separated arguments appear
● The number and type of arguments should match the number of function
parameters
● Each argument is an expression whose type should match the type of the
corresponding parameter in the function interface (prototype)
● When a function call is executed,
○ the arguments are first evaluated and their resulting values are assigned
to the corresponding parameters
○ The function body is then executed
○ Finally the return value (if any) is passed to the caller

Chapter_One_Functions 2
3
Calling a function cont’d
● A function call in C++ is like a detour on a highway
● Imagine that you are traveling along the “road” of the primary
function called main()
● When you run into a function-calling statement, you must
temporarily leave the main() function and execute the function
that was called
● After that function finishes (its return statement is reached),
program control returns to main()
● In other words, when you finish a detour, you return to the
“main” route and continue the trip
● Control continues as main() calls other functions
Chapter_One_Functions 2
4
Dclaring, Defining and Calling a Function Example

Chapter_One_Functions 2
5
Given the next program, which function is the calling
function and which is the called function?

#include<iostream>
void nextMsg();
int main()
{
cout<< “Hello!\n”;
nextMsg();
return 0;
void nextMsg() {
}
cout<< “GoodBye!\n”;
return;
}

2
Chapter_One_Functions
6
 Takeaway questions:
i. What parameter does starLine() expect?
ii. Trace the code and show the output
Chapter_One_Functions
2
7
Function parameters and arguments
● The formal parameters (is used as a kind of blank, or place
holder, to stand in for the argument)
● are list of variables used by the function to perform its task, and
● the arguments passed to the function during calling of a function
are values sent to the function
● The arguments of function calling can be using either of the two
supported styles in C++: passing by value or passing by
reference.
Passing by value:
● A value parameter receives a copy of only the value of the
argument passed to it
● As a result, if the function makes any changes to the parameters,
this will not affect the argument, for instance (see next slide)

Chapter_One_Functions 2
8
#.....
void func(int);//prototype
int main()
{ int x = 10;
cout<< “ Before call to function doublingFunc x = “
<<x<<endl;
doublingFunc(x);
cout<< “ After call to function doublingFunc x = “
<<x<<endl;

void doublingFunc(int num)

return 0; { num *= 2;
}
cout<< “num = ” << num << endl;
}

Chapter_One_Functions
2
9
Pass by value
● The single parameter of doubleFunc is a value parameter
● As far as this function is concerned, num behaves just like a local variable inside
the function
● When the function is called and x passed to it, num receives a copy of the value
of x
● As a result, although num is doubled by the function, this does not affect x
● The program produces the following output:

Before call to function doublingFunc x = 10

num = 20

After call to function doublingFunc x = 10

● Passing arguments in this way, where the function creates copies of the
arguments passed to it is called passing by value

Chapter_One_Functions
3
0
Pass by reference
● A reference parameter, on the other hand, receives the
argument passed to it and works on it directly
● Any change made by the function to a reference
parameter is in effect directly applied to the argument
● Passing parameters in this way is called
pass-by-reference
● Taking the same example with pass by reference
(next slide)

Chapter_One_Functions
3
1
#.....
void func(int&);//prototype
int main()
{
int x = 10;
func(x);
cout<< “ x = ”<<x<< endl;

return 0;
} void func(int & num)
{
num += 10;
cout<< “num = ” << num <<endl;
}

Chapter_One_Functions
3
2
Pass by reference cont’d
● The parameter of func is a reference parameter
(previous slide);
● num corresponds to x for this specific program as it x is sent
by its reference and not its value
● Any change made on num will be made to x. Thus, the
program produces the following output:
num = 20
x = 20
● Suppose you have pairs of numbers in your program
and you want to be sure that the smaller one always
precedes the larger one.
● To do this, you call a function, order(), which checks two
numbers passed to it by reference and swaps the originals if
the first is larger than the second.

Chapter_One_Functions
3
3
Takeaway question: Trace the code above and show the output
3
Chapter_One_Functions
4
Pass by reference cont’d
● Using reference arguments in this way is a sort of remote
control operation.
● The calling program tells the function what variables in the
calling program to operate on, and the function modifies these
variables without ever knowing their real names
● Takeaway question: what do you do when you want to
pass by reference and yet you don’t want the source to be
modified?

3
Chapter_One_Functions
5
Global vs local variables
● Everything defined at the program scope level (outside functions)
is said to have a global scope
○ Eg.

int year = 1994; //global variable

int max( int, int ); //global function
int main ( void )
{
//…
}
● Global variables are visible (“known”) from their point of
definition down to the end of the program.
Chapter_One_Functions 3
6
Local variables
● Each block in a program defines a local scope
● Thus the body of a function represents a local scope
● The parameters of a function have the same scope as the function body
● Variables defined within a local scope are visible to that scope only
● Hence, a variable need only be unique within its own scope Local scopes
may be nested, in which case the inner scope overrides the outer scopes
int xyz; // xyz is global
void Foo ( int xyz ) // xyz is local to the body of Foo
{ if(xyz > 0){
double xyz; // xyz is local to this block
…
}
}

Chapter_One_Functions
3
7
Scope operator
● Because a local scope overrides the global scope, having a local
variable with the same name as a global variable makes the latter
inaccessible to the local scope.
● Takeaway question: what do you do to reverse such overriding?
Eg

int num1;

void fun1(int num1)

//…

Chapter_One_Functions
3
8
Scope operator cont’d
Solution???
● Use scope operator ‘::’ which takes a global entity as argument.
int num1 = 2;//global variable

void fun1(int num1) {

//…

num1=33; //local variable

cout<<num1; // the out put will be 33

// why? Because local variable overrides global variable

cout<<::num1; //the out put will be 2 which is the global

if(::num1 != 0)//num1 here refers to global num1

//…

}
Chapter_One_Functions 3
9
Automatic vs static variables
• describe what happens to local variables when control
returns back to the calling function.
• By default, all local variables are automatic

○ Are erased when the function ends

○ They use prefix auto

Eg. main()
{
int i;
auto float x;
…
}

Chapter_One_Functions 4
0
Automatic vs static variables cont’d
● The opposite of an automatic is a static variable
● All global variables are static and
● all static variables retain their values
● Therefore, if a local variable is static, it too retains its value
when its function ends -in case this function is called a second
time.
● static is a keyword to declare a static variable
● Static variables can be declared and initialized within the
function, but the initialization will be executed only once
during the first call.
● If static variables are not initialized explicitly, they will be
initialized to 0 automatically

Chapter_One_Functions
4
1
Takeaway question: Trace the code above and show the output
Chapter_One_Functions 4
2
 inline functions
● Suppose that a program frequently requires finding the absolute
value of an integer quantity
● For a value denoted by n, this may be expressed as:
(n > 0 ? n : -n)
● Solution? to define it as a function:
int Abs ( int n ){
return n > 0 ? n : -n; }
● The disadvantage of the function version is substantial overhead
■ Extra time and space used to invoke function, pass parameters, allocate
storage for its local variables, store the current variable, etc.

Chapter_One_Functions
4
3
● Solution??? defining as an inline function
● The effect of this is that when Abs is called, the compiler, instead of
generating code to call Abs, expands the program body and substitutes
the body of Abs in place of the call.

inline int Abs ( int n )

{
return n > 0 ? n : -n;
}
void main ( )
{
cout<<Abs(-10); //n>0?n:-n
}

Chapter_One_Functions 4
4
inline functions cont’d
● Not every function can be inlined. Some typical reasons why inlining
is sometimes not done include:
■ the function calls itself, that is, is recursive
■ the function contains loops such as for(;;) or while()
■ the function size is too large
● Another good reason to inline is that you can sometimes speed up
your program by inlining the right function
● Most of the advantage of inline functions comes from avoiding the
overhead of calling an actual function
● Concerning inline functions, the compiler is free to decide whether a
function qualifies to be an inline function
● If the inline function is found to have larger chunk (amount) of code,
it will not be treated as an inline function, but like other normal
functions.
Chapter_One_Functions
4
5
 Default arguments and function overload
● C++ has two capabilities that regular C doesn’t have- Default
arguments and function overloading
● Default argument is a programming convenience which removes
the burden of having to specify argument values for all function
parameters
● You might pass a function an error message that is stored in a
character array, and the function displays the error for a certain
period of time. The prototype for such a function can be this:
Void pr_msg(char note[]);
● Therefore, to request that pr_msg() display the line ‘Turn printer
on’, you call it this way:
Pr_msg(“Turn printer on”);

Chapter_One_Functions 4
6
Default arguments and function overload …
● As you write more of the program, you begin to realize that you
are displaying one message-for instance, the ‘Turn printer on’
msg-more often than any other message.
● Instead of typing the argument Turn printr on over and over
when calling the function over and over, to get the message
displayed, you can set up the prototype for pr_msg() so that it
defaults to the ‘turn printer on’ message in this way:
void pr_msg(char note[] = “Turn printr on”);
● This makes your programming job easier. Because you would
usually want pr_msg() to display ‘turn printer on’, the default
argument list takes care of the message and you don’t have to
pass the message when you call the function

4
Chapter_One_Functions
7
Default arguments and function overload …

Chapter_One_Functions 4
8
Default arguments and function overload …
• parameters with default should always be at
the right side of function declaration
• Takeaway question: Which of the following
function definitions with default paramenter is
correct?
void Mult_Dispaly (int x, int y=70, int z) {

cout<< (x*y*z)<<endl; }
void MultDispaly (int x, int z, int y=70) {

cout<< (x*y*z)<<endl; }
Suppose you call MultDisplay(5, 2);// what will be displayed?

Chapter_One_Functions
4
9
Overloaded functions
● Unlike C, C++ lets you have more than one function
with the same name
● Functions with the same name are called overloaded
functions
● C++ requires that each overloaded functions differ in
its argument list
● C++ allows you to give two or more different
definitions to the same function name, which means
you can reuse names that have strong intuitive appeal
across a variety of situations
● Overloaded functions enable you to have similar functions
that work on different data (number or type)
● if two or more functions differ only in their return types,
Chapter_One_Functions
5
C++ can’t overload them, should have different names 0
Overloaded functions cont’d
● Suppose that you write a function that return the absolute value
of what ever number you passed to it; which one of the
following implementations involves function overload?

int iAbs(int a) { int Abs(int a){

if(a<0) if(a<0)
return (a*-1); return a*-1;
else
else return a; }
return (a); } float Abs(flaot x){
float fAbs(float x) { if(x<0.0)
if(x<0.0) return x*-1.0;
return (x * -1.0); else
else return x;}
return (x); }

5
Chapter_One_Functions
1
Overloaded functions cont’d
● Takeaway question: the following program demonstrates function overload to
compute and display average of two or three numbers passed to it; What will be the
output? How does the compiler decide which definition to invoke during function
call?

5
Chapter_One_Functions
2
Overloaded functions cont’d
• What will be the output of the following? Hint:
consider the possibility of automatic type
conversion.

5
Chapter_One_Functions
3
 Recursion
● A function which calls itself is said to be recursive
function
● Recursion is a general programming technique applicable
to problems which can be defined in terms of themselves
● Recursive problem-solving approaches have a number of
elements in common.
● A recursive function is called to solve a problem.
● The function knows how to solve only the simplest case(s), or so-called
base case(s)
● If the function is called with a base case, the function simply returns a
result.
● If the function is called with a more complex problem, it typically divides
the problem into two conceptual pieces—a piece that the function knows
how to do and a piece that it does not know how to do.
Chapter_One_Functions
5
4
 Recursion
● To make recursion feasible, the latter piece must resemble
the original problem, but be a slightly simpler or smaller
version
● This new problem looks like the original, so the function
calls a copy of itself to work on the smaller problem—this is
referred to as a recursive call and is also called the
recursion step
● The recursion step often includes the keyword return,
because its result will be combined with the portion of the
problem the function knew how to solve to form the result
passed back to the original caller, possibly main
● The recursion step executes while the original call to the
function is still “open,” i.e., it has not yet finished executing
Chapter_One_Functions
5
5
 Recursion
● Example
● Take the factorial problem, for instance which is defined as:

○ factorial of 0 is 1

○ factorial of a positive number n is n time the factorial of n-1

unsigned int factorial(unsigned int n )

return n = = 0 ? 1 : n * factrial ( n-1);

Chapter_One_Functions
5
6
Chapter_One_Functions
5
7
Recursion cont’d
● The stack frames for these calls appear sequentially on the
runtime stack, one after the other
● Stack frame – The section of memory where the local
variables, arguments, return address and other
information of a function are stored, is called stack
frame or activation record
● A recursive function must have at least one termination
condition which can be satisfied
● Otherwise, the function will call itself indefinitely until
the runtime stack overflows

Chapter_One_Functions
5
8
Recursion cont’d
• The three necessary components in a recursive method are
− A test to stop or continue the recursion
− An base case or end case that terminates the recursion
− A recursive call(s) that continues the recursion
• let us implement two more mathematical functions
using recursion
• e.g the following function computes the sum of the first N positive
integers 1,2,…,N. Takeaway question: What other name do you have
for such series?
• Notice how the function includes the three necessary components of a
recursive method (next slide)

Chapter_One_Functions
5
9
Recursion cont’d
int sum(int N) {
if(N==1)
return 1;
else
return N+sum(N-1);
}
• Takeaway question: implement the above logic
iteratively (using for loop)
Chapter_One_Functions 6
0
 Recursion cont’d
• Define a recursive function that computes the exponentiation An where
A is a real number and N is a positive integer.
• The function expects two arguments, A and n.
• the value of A will not change in the calls, but the value of n is
decremented after each recursive call
float expo(float A, int n) {
if(N==1)
return A;
else
return A * expo(A,N-1);
}
• Takeaway question: implement the same logic iteratively

Chapter_One_Functions 6
1
Recursion cont’d
● Try to use a recursive function call to solve the Fibonacci
series. The Fibonacci series is :
− 0,1,1,2,3,5,8,13,21,…
● The recursive definition of the Fibonacci series is as follows
○ Fibonacci (0) =0
○ Fibonacci (1) =1
○ Fibonacci (n) =Fibonacci (n-1) +Fibonacci (n-2);

○ Takeaway question: define a Fibonacci function that

implements the Fibonacci series (Example next slide)

Chapter_One_Functions 6
2
Takeaway question: Trace the code above and show the output
6
3
 Recursion vs Iteration
● Both iteration and recursion are based on control structure.
○ Iteration uses a repetition structure (such as for, while, do…while) and
○ recursive uses a selection structure (if, if else or switch).
● Both iteration and recursion involve repetition: Iteration explicitly uses a repetition
structure; recursion achieves repetition through repeated method calls or function calls.
● Iteration and recursion each involve a termination test: Iteration terminates when the
loop-continuation condition fails; recursion terminates when a base case is recognized
● Both iteration and recursive can execute infinitely-an infinite loop occurs with iteration if
the loop continuation test become always true or loop termination condition cannot be
met. And infinite recursion occurs if the recursion step doesn’t reduce the problem in a
manner that converges on a base case.
● Recursion has disadvantage as well. It repeatedly invokes the mechanism, and
consequently the overhead of method calls. This can be costly in both processor time and
memory space. Each recursive call creates another copy of the method (actually, only the
function’s variables); this consumes considerable memory.

Chapter_One_Functions
6
4
Recursion vs iteration cpnt’d
● N.B: Use recursion if:
○ A recursive solution is natural and easy to
understand
○ A recursive solution doesn’t result in excessive
duplicate computation.
○ the equivalent iterative solution is too complex and
○ of course, when you are asked to use one in
the exam!!

Chapter_One_Functions
6
5
End of Chapter One

Chapter_One_Functions
6
6