Lecture 8

RECURSIVE FUNCTIONS
Recursion
 When function call itself repeatedly ,until some specified condition is
met then this process is called recursion.
 It is useful for writing repetitive problems where each action is
stated in terms of previous result.
 The need of recursion arises if logic of the problem is such that the
solution of the problem depends upon the repetition of certain set
of statements with different input values an with a condition.
2 Main conditions

Two basic requirements for recursion :

1. The function must call itself again and again.
2. It must have an exit condition.
(EXAMPLE)Factorial using recursion

int rec(int a)
void main()
{
{
int b;
int rec(int);
if(a<=1)
int n, fact;
{
cout<<“enter the no.”;
return(1);
cin>>n;
}
fact=rec(n);
else
cout<<“factorial is”<<fact;
{
getch();
b=a*rec(a-1);
}
return(b);
}}
• Output:
Enter a number=3
Factorial0f 3=6
Stack representation

.
. 3*2*fact(1)
3*fact(2) 3*fact(2)
fact(3) fact(3)
fact(3)

3*2*1
3*2*fact(1)
3*fact(2)

fact(3)
Fibonacci using recursion
int main()
{
int fib(int);
int n;
cout<<“enter the number of terms=“;
cin>>n;
for(int i=1;i<=n;i++)
cout<<fib(i)<<“ “;
getch();
return o;
}
int fib(int m)
{
if(m==1|| m==2)
return(1);
else
return(fib(m-1)+fib(m-2));
}
Advantages of recursion
1. It make program code compact which is easier to
write and understand.
2. It is used with the data structures such as
linklist,stack,queues etc.
3. It is useful if a solution to a problem is in repetitive
form.
4. The compact code in a recursion simplifies the
compilation as less number of lines need to be
compiled.
Disadvantages

1. Consume more storage space as recursion calls and automatic

variables are stored in a stack.
2. It is less efficient in comparison to normal program in case of speed
and execution time
3. Special care need to be taken for stopping condition in a recursion
function
4. If the recursion calls are not checked ,the computer may run out of
memory.
FUNCTION
OVERLOADING
Polymorphism
• The word polymorphism is derived from Greek word Poly which
means many and morphos which means forms.
• Polymorphism can be defined as the ability to use the same name for
two or more related but technically different tasks.
• Eg-woman plays role of daughter,sister,wife,mother etc.
Overloading in C++
❑What is overloading
– Overloading means assigning multiple
meanings to a function name or operator
symbol
– It allows multiple definitions of a function with the same name, but
different signatures.
❑C++ supports
– Function overloading
– Operator overloading
Why is Overloading Useful?
❑ Function overloading allows functions that
conceptually perform the same task on
objects of different types to be given the
same name.

❑ Operator overloading provides a convenient

notation for manipulating user-defined
objects with conventional operators.
Function Overloading
• Is the process of using the same name for two or more functions
• Requires each redefinition of a function to use a different function
signature that is:
• different types of parameters,
• or sequence of parameters,
• or number of parameters
• Is used so that a programmer does not have to remember multiple
function names
Function Overloading
• Two or more functions can have the same name but different
parameters
• Example:
int max(int a, int b) float max(float a, float b)
{ {
if (a>= b) if (a>= b)
return a; return a;
else else
return b; return b;
} }
Overloading Function Call Resolution
❑ Overloaded function call resolution is done by
compiler during compilation
– The function signature determines which definition
is used
❑ a Function signature consists of:
– Parameter types and number of parameters
supplied to a function
❑ a Function return type is not part of function signature
and is not used in function call resolution
void sum(int,int);
void sum(double,double);
void sum(char,char);
void main()
{
int a=10,b=20 ;
double c=7.52,d=8.14;
char e=‘a’ , f=‘b’ ;
sum(a,b); //calls sum(int x,int y)
sum(c,d); //calls sum (double x,double y)
sum(e,f); // calls sum(char x,char y)
}
void sum(int x,int y)
{
vout<<“\n sum of integers are”<<x+y;
}
void sum(double x,double y)
{
cout<<“\n sum of two floating no are”<<x+y;
}
void sum(char x,char y)
{
cout<<“\n sum of characters are”<<x+y;
}
• Output:
Sum of integers 30
sum of two floating no are 15.66
sum of characters are 195
Void area(int)
Void area(int,int);
Void area(int,int,int);
Int main()
{
Int side=10,le=5,br=6,a=4,b=5,c=6;
Area(side);
Area(le,br);
Area(a,b,c);
Getch();
Return 0;
}
Void area(int x)
{ cout<<“area is”<<x*x;
}
Void area(int x,int y)
{cout<<“area of rectang;e”=<<x*y;
}
Void area(int x,int y,int z)
{cout<<“volume is”<<x*y*z;
}
SCOPE RULES
Scope

• The scope of a variable is the portion of a program

where the variable has meaning (where it exists).
• A global variable has global (unlimited) scope.
• A local variable’s scope is restricted to the function
that declares the variable.
• A block variable’s scope is restricted to the block in
which the variable is declared.
Understanding Scope
• Some variables can be accessed throughout an entire program, while
others can be accessed only in a limited part of the program
• The scope of a variable defines where it can be accessed in a program
• To adequately understand scope, you must be able to distinguish
between local and global variables
Local variables
• Parameters and variables declared inside the definition of a function
are local.
• They only exist inside the function body.
• Once the function returns, the variables no longer exist!
• That’s fine! We don’t need them anymore!
Block Variables
• You can also declare variables that exist only within the body of a
compound statement (a block):
{
int foo;
…
…
}
Global variables
• You can declare variables outside of any function definition – these
variables are global variables.
• Any function can access/change global variables.
• Example: flag that indicates whether debugging information should
be printed.
Distinguishing Between Local
and Global Variables
• Celebrity names are global because they are known
to people everywhere and always refer to those
same celebrities
• Global variables are those that are known to all
functions in a program
• Some named objects in your life are local
• You might have a local co-worker whose name
takes precedence over, or overrides, a global one
A note about
Global vs. File scope
• A variable declared outside of a function is available everywhere, but
only the functions that follow it in the file know about it.

• The book talks about file scope, I’m calling it global scope.
Block Scope
int main(void) {
int y;

{
int a = y;
cout << a << endl;
}
cout << a << endl;
}