CSI247:
Data Structures
Lecture 05 – Recursion
Department of Computer Science
B. Gopolang (247-275)
Previous lesson
• Growth rate of an algorithm
• Time complexity of an algorithm (Big-O)
2
Learning Objectives
● By the end of this lecture you must be able to:
• Differentiate between recursion and a
recursive method
• Understand the 2 cases required in any
recursive method implementation
• Implement a recursive method
• Trace a recursive method
3
Introduction
● Rem:
• Methods are written to solve problems
• Method is a collection of related statements
● Recursion: A programming technique in
which a method call itself to solve a problem
• Associated with repetition
● Recursive method: A method implemented
using recursion
4
Implementing recursion
● Rem:
• A recursive method calls itself to solve a
problem
● A recursive method MUST implement 2 cases
a) Base case: a simple case that can be
answered without using recursion.
• Its purpose: to stop recursion
b) Recursion case: method must call itself
(making a recursive call) to help compute the
final answer 5
Example: factorial
● Often denoted as n!
● A classical example of recursion
● E.g.: n! = 1· 2· 3 ··· (n-1)· n
• Defn: The product of all numbers between 1
& n, inclusive.
● Mathematically:
1 if n = 0 (Base case)
f(n) =
n . f(n-1) otherwise (Recursive case)
= n* (n-1)* (n-2) * (n-3) * …. * 1
E.g. 5! = 5 * 4 * 3 * 2 * 1 = 120 6
Implementing n!
a) Using iteration
● Rem n! = n* (n-1) * (n-2) * (n-3) * …. * 1
public static long factL(int in) {
long prod = 1;
for (int i=1; I <= n; i++) {
prod = prod *= i;
}
return prod;
}
7
b) Using recursion
public static long factR(int in) {
long prod = 1;
if (n==1)
prod = 1;
else
prod = n * factR(n-1);
return prod;
}
NOTE: method factR is defined in terms of
another factR, until base case is reached (0 in
8
Important points…
● Base cases
• Test for all possible base cases (need at least 1)
• Every possible chain of recursive calls must
reach a base case
• Base case should not use recursion
● Recursive calls
• 1 recursive call performed at a time
• Only 1 recursive option must be executed if
there are several options
• Each possible recursive call must progress
towards a base case 9
Tracing recursive methods
● E.g.: factR(5)
if (5 == 1)
return 1;
else
return 5 * factR(4) 5*4*3*2*1
return 4 * factR(3) 4*3*2*1
return 3 * factR(2) 3*2*1
return 2 * factR(1) 2*1
(Base case reached!) 10
Recursion vs Iteration
● Every recursion solution has a corresponding iterative
solution.
• You can re-write from iterative to recursive,
& vise versa
● Problem with recursion:
• Overhead associated with multiple method calls.
• However, for some problems recursive solutions
are often more simple and elegant than iterative
solutions.
Note:
● Need to determine when recursion is appropriate!
11
Infinite recursion
● Cause?
● Missing base case
● E.g.:
• Let us modify method factR to result in an
infinite recursion
//Can you see base case?
public long factR(int n) {
long prod;
prod = n * factR(n – 1);
return prod;
}
12
Exercises
a) Type fact & factR code segments provided in
the handout. Fix errors, if any. Compile and run
them.
b) Is there any difference between output from
the non-recursive and the recursive one?
c) Write recursive method power, which takes
int variables x and y, and returns xy
d) Convert method in c) above to its non-
recursive version
e) Test methods in c) and d) above. They should
give the same output 13
e) Write non-recursive method fibonnaci, that
accepts a positive int value and display the
fibonacci series for that int value
• Fibonacci series: a sequence of numbers
starting with 0 and 1, in which each number is
the sum of its 2 preceding numbers
f) Convert method in e) to its recursive version
g) Trace the following method calls:
• factR(7)
• power(6, 3)
• fibonacci(6) // the recursive version 14
Summary
• In this lesson, we were able to do these:
• Differentiated between recursion and a recursive
method
• Identified the two cases required when
implementing recursion
• Implemented a recursive method
• Traced a recursive method call
• Illustrated infinite recursion using an example
• For improving human lives
14
Next lesson
• Searching Arrays …
15
Q &A
16
