BSc Hons in Software Engineering
CMP110240 – Programming Fundamentals
Recursion
<copyright notice – copyrighted to LNBTI>
ACKNOWLEDGEMENT
Presented by: Ms Nimali Hettiarachchi
Contributors:
Ms Ridmi Wimalasiri
Reviewed by: Ms Nimali Hettiarachchi
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 2
RESOURCES
• Course page of the course
• References available for the course.
• Online resources for the section
o https://www.w3schools.com/cpp/cpp_functions_recursion.asp
o https://www.programiz.com/cpp-programming/recursion
o https://www.geeksforgeeks.org/cpp-recursion/
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 3
What is Recursion?
•Recursion in C++ is a
technique in which a function
calls itself repeatedly until a
given condition is satisfied.
•Recursion is the process of
solving a problem by
breaking it down into smaller,
simpler sub-problems.
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 4
What is Recursion?
Recursive Function
• A function that calls itself is called a recursive function. When a recursive
function is called, it executes a set of instructions and then calls itself to
execute the same set of instructions with a smaller input. This process
continues until a base case is reached, which is a condition that stops the
recursion and returns a value.
Base Condition
• The base condition is the condition that is used to terminate the
recursion. The recursive function will keep calling itself till the base
condition is satisfied.
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 5
Recursive Case
Recursive case is the way in which the
recursive call is present in the function.
Recursive case can contain multiple recursive
calls, or different parameters such that at the
end, the base condition is satisfied and the
recursion is terminated.
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 6
Example 1
int Sum(int n)
{
// base condition to terminate the recursion when N = 0
if (n == 0) {
return 0;
}
// recursive case / recursive call
int res = n + Sum(n - 1);
Edges
return res;
}
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 7
Example 2
int factorial(int n) {
// Factorial of 0 or 1 is 1
if (n == 0 || n == 1)
return 1;
// Recursive case: factorial of n is n multiplied by factorial
of (n-1) Edges
return n * factorial(n - 1);
}
Data Structure & Algorithms | Graphs Theory | Introduction to Graphs 8
