Recursion
Dr. Samantha Rajapaksha
Head/Department of IT
Senior Lecturer(HG)
B.Sc. M.Sc. Ph.D.
04/20/2024 Dr. Samantha Rakapaksha 1
Recursion –Example 1
Factorial
n ! = n * (n -1) * (n -2) * ... * 2 * 1, and that 0! = 1.
A recursive definition is
(n)! = {n * (n -1)! if n > 0}
{1 if n = 0}
Factorial -A graphical view
n!
n * (n-1)! We know
0! So we
can build
(n-1) * (n-2)! the tree
backward
1!
1 * 0!
Exercise
• Draw the recursive tree for 5!
• How does it calculate 5! ? Is it:
Bottom to top calculation or
Bu
5! ild Top to bottom calculation ?
the
5 * 4! an
sw
er
fr o
4 * 3! m
bo
tto
3 * 2! m
to
t op
2 * 1!
1 * 0!
initial
condition
Factorial(contd.)
(n)! = {n * (n -1)! if n > 0}
{1 if n = 0}
int factorial(int n) { Compare
if (n == 0)
return 1;
else
return (n * factorial(n-1));
}
Recursion
What is recursion?
A function that calls itself directly or indirectly to solve a smaller
version of its task until a final call which does not require a self-call is
a recursive function.
Recurrence equation
• Mathematical function that defines the running
time of recursive functions.
• This describes the overall running time on a
problem of size n in terms of the running time on
smaller inputs.
Ex: T(N) = T(N-1) + b
T(N) = T(N/2) + c
Recurrence - Example1
Find the Running time of the following function
int factorial(int n) {
if (n == 0) //A
return 1; //B
else
return (n * factorial(n -1)); //C
}
Statement A takes time a for the conditional evaluation
Statement B takes time b for the return assignment
Statement C takes time:
c for the operations(multiplication & return)
T(n-1) to determine (n-1)!
Recurrence - Example1 (Contd.)
T(n) = Time to execute A & C
T(n) = a + c + T(n-1)
• This method is called iteration method (or repeated
substitution)
Exercise
• Solve the recurrence
T(n) = T(n/2) + 2
You are given that
n = 16 and
T(1) = 1
Solve the recurrence
T(n) = 2T(n/2) + cn and T(1) = 1 where c is a contant
Finding a solution to a recurrence.
• Other methods
• Recursion tree.
• Master Theorem.
Write the recursive algorithm.
reference
• Discrete Mathematics with Applications 4th Edition
• by Susanna S. Epp (Author)
