C++ Functions
Mandar Padhye
Recap
• Need of breaking tasks into sub-tasks
• C++ Functions
• Function signature and return value
• Function declaration and definition
• Default Parameters
• Do’s and Dont’s
Polymorphism: Function Overloading
• Polymorphism: having different forms.
• In C++ Polymorphism can be applied to functions and operators.
• Functions or operators that behave differently in different context.
• Compile time and run-time Polymorphism
• Function overloading: Compile time Polymorphism
• Functions having same names and different signatures, are so-called overloaded functions
• Signature comprises of function name and parameters.
Function Overloading
//Function for adding two integers int main() {
void add(int a, int b) {
// add() with int values invoked
cout << "Integer Sum = ";
cout << a + b << endl; add(10, 2);
} // add() with double value invoked
// Function to add two floating add(5.3, 6.2);
point values return 0;
void add(double a, double b) { }
cout << "Float Sum = ";
cout << a + b << endl ;
}
Recursion
• Function calling itself directly or indirectly
e.g.
void foo(int n) {
...
foo(n-1);
...
}
Mutual recursion
void foo1(int n){
...; foo2(n-2); ...
}
void foo2(int n){
...; foo1(n-1); ...
}
Recursion
• When to use recursion
• When a problem can be divided into smaller problems of same type
• Definition of a concept includes the concept itself
• When solution demands backtracking: i.e. trying certain branch for traverse, retract if the branch proves to be
wrong.
• Data Processing for hierarchical formats. i.e. html, xml etc.
• Recursion Key principles:
• Base case: Its a simplest scenario where function does not call itself. Without a base case, it will lead to infinite
recursion, which will result into program termination due to stack overflow.
• Recursive case: All other cases where the function reduces the problem scope and calls itself. Code of the
recursive case must ensure that the problem will eventually be reduced to the base case.
Recursion
int factorial(int n){
if(n == 0) return 1;
return n * factorial(n-1);
}
int Fibonacci(int n) {
if (n <= 1) {
return n; // Base cases: F(0) = 0, F(1) = 1
return Fibonacci(n - 1) + Fibonacci(n - 2); // Recursive relation
}
Recursion Vs Iteration
• One can always replace recursive code with iterative code
• Recursion is costlier than iteration. It pushes all the local variables to call stack, creates fresh copy of
variable for each recursion.
• Depth of recursion is limited by the computational resources
• Use Iteration wherever possible
• Use recursion when iterative solution becomes very complex, while recursive one is elegant
• e.g. towers of Hanoi, html/xml parsing, path finding in maze...
• When using recursion, make sure that the base case is eventually reached.
• When using recursion, you should have estimate of what will the max depth of recursion be.
Recap...
• Function Signature
• Function overloading
• Recursion
• base case, recursive case
• Iterative code Vs Recursive code
Problem Statements
1. Using recursion, write a program to print Fibonacci sequence.
2. Write a pseudo code for solving towers of Hanoi problem.
Questions/discussions
