Presentation for use with the textbook Data Structures and

Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia,

and M. H. Goldwasser, Wiley, 2014

Recursion

© 2014 Goodrich, Tamassia, Goldwasser Recursion 1

What is Recursion?
❑ Recursion: is the concept of defining a
method that makes a call to itself (a
recursive call).
❑ A recursive method, is a method that
calls itself.

2
What is Recursion - 2
❑ Does it do exactly the same thing???
◼ → Logic (instructions) are exactly the same.
◼ → Conditions (e.g. parameters, state of
data, etc.) are different.

❑ Like iteration, recursion is a means for

repetition
◼ Eventually the repetition must stop!
◼ → The repetitive steps must work towards the
stopping case(s).
3
Classic Example–
The Factorial Function
❑ n! = n * (n-1) * (n-2) * … * 3 * 2 * 1

❑ Factorial definition:

 1 if n = 0
f ( n) = 
n  (n − 1)  (n − 2) 3  2 1 n  1

❑ What is 4! ?
◼ 4! = 4 * 3 * 2 *1
=4*?

5 Using Recursion
Classic Example–
The Factorial Function
❑ Recursive definition:

 1 if n = 0
f ( n) = 
n  f (n − 1) n 1

❑ As a Java method:
// recursive factorial function
public static int recursiveFactorial(int n) {
if (n == 0) return 1;
else return n * recursiveFactorial(n- 1);
}

6 Using Recursion
 A Closer Look

❑ As a Java method:
// recursive factorial function

public static int recursiveFactorial(int n) {

Base
Case(s) if (n == 0) return 1;

else return n * recursiveFactorial(n- 1);

}

7 Using Recursion
 A Closer Look

❑ As a Java method:
// recursive factorial function

public static int recursiveFactorial(int n) {

Base
Case(s) if (n == 0) return 1;

Recursive
Case(s) else return n * recursiveFactorial(n- 1);

8 Using Recursion
}
 Content of a Recursive Method
❑ Base case(s)
◼ Values of the input variables for which we perform
no recursive calls are called base cases (there
should be at least one base case).
◼ Every possible chain of recursive calls must
eventually reach a base case.
❑ Recursive calls
◼ Calls to the current method.
◼ Each recursive call should be defined so that it
makes progress towards a base case.

© 2014 Goodrich, Tamassia,

Recursion Goldwasser 9
 Recursive Factorial

We trace recursiveFactorial(4) in class

© 2010 Goodrich, Tamassia 10 Using Recursion

 Visualizing Recursion Runtime??

❑ Recursion trace ❑ Example

◼ A box for each call
return 4*6 = 24 final answer
recursive call
recursiveFactorial (4)
◼ An arrow from each call return 3*2 = 6
caller to callee recursiveFactorial (3)

◼ An arrow from each call return 2*1 = 2

callee to caller recursiveFactorial (2)

showing return value call return 1*1 = 1

recursiveFactorial (1)

call return 1

recursiveFactorial (0)

© 2014 Goodrich, Tamassia,

Recursion Goldwasser 11
 Visualizing Binary Search
❑ We consider three cases:
◼ If the target equals data[mid], then we have found the target.
◼ If target < data[mid], then we recur on the first half of the
sequence.
◼ If target > data[mid], then we recur on the second half of the
sequence.

© 2014 Goodrich, Tamassia, Goldwasser Recursion 12

 Binary Search Runtime??
Search for an integer in an ordered list

© 2014 Goodrich, Tamassia, Goldwasser Recursion 13

 Analyzing Binary Search
❑ Runs in O(log n) time.
◼ The remaining portion of the list is of size
high – low + 1
◼ After one comparison, this becomes one of
the following:

◼ Thus, each recursive call divides the search

region in half; hence, there can be at most
log n levels
© 2014 Goodrich, Tamassia, Goldwasser Recursion 14
Types of Recursion
❑ Depending on the number of recursive calls
performed each time a recursive method is
invoked there are 3 types:
1. Linear recursion
→ at most one recursive call.
2. Binary recursion
→ at most two recursive calls.
3. Multiple recursion
→ a method may initiate multiple recursive
calls 15
 Binary Recursion Example 1
❑ Problem: add all the numbers in an integer array A:
Algorithm BinarySum(A, i, n):
Input: An array A and integers i and n
Output: The sum of the n integers in A starting at index i
if n = 1 then
return A[i]
return BinarySum(A, i, n/ 2) + BinarySum(A, i + n/ 2, n/ 2)

❑ Example trace: 0, 8

0, 4 4, 4
0, 2 2, 2 4, 2 6, 2

0, 1 1, 1 2, 1 3, 1 4, 1 5, 1 6, 1 7, 1

© 2014 Goodrich, Tamassia, Goldwasser Recursion 16

 Binary Recursion Example 2
❑ Fibonacci numbers are defined recursively:
F0 = 0
F1 = 1
Fi = Fi-1 + Fi-2 for i > 1.
❑ Recursive algorithm (first attempt):
Algorithm BinaryFib(k):
Input: Nonnegative integer k
Output: The kth Fibonacci number Fk
if k = 1 then
return k
else
return BinaryFib(k − 1) + BinaryFib(k − 2)

© 2014 Goodrich, Tamassia, Goldwasser Recursion 17

 Multiple Recursion Example
Initial call

PuzzleSolve (3,(),{a,b,c})

PuzzleSolve (2,a,{b,c}) PuzzleSolve (2,b,{a,c}) PuzzleSolve (2,c,{a,b})

PuzzleSolve (1,ab,{c}) PuzzleSolve (1,ba,{c}) PuzzleSolve (1,ca,{b})

abc bac cab

PuzzleSolve (1,ac,{b}) PuzzleSolve (1,bc,{a}) PuzzleSolve (1,cb,{a})
acb bca cba

© 2014 Goodrich, Tamassia, Goldwasser Recursion 18

 Linear Recursion
❑ Test for base cases
◼ Begin by testing for a set of base cases (there should be
at least one).
◼ Every possible chain of recursive calls must eventually
reach a base case, and the handling of each base case
should not use recursion.
❑ Recur once
◼ Perform a single recursive call
◼ This step may have a test that decides which of several
possible recursive calls to make, but it should ultimately
make just one of these calls
◼ Define each possible recursive call so that it makes
progress towards a base case.
© 2014 Goodrich, Tamassia, Goldwasser Recursion 19
 Reversing an Array
Algorithm reverseArray(A, i, j):
Input: An array A and nonnegative integer
indices i and j
Output: The reversal of the elements in A
starting at index i and ending at j

if i < j then Runtime??

Swap A[i] and A[ j]
reverseArray(A, i + 1, j − 1)
return
© 2014 Goodrich, Tamassia, Goldwasser Recursion 20
 Defining Arguments for Recursion
❑ In creating recursive methods, it is important to define the
methods in ways that facilitate recursion.
❑ This sometimes requires we define additional parameters
that are passed to the method.
❑ For example, we defined the array reversal method as
reverseArray(A, i, j), not reverseArray(A)

© 2014 Goodrich, Tamassia, Goldwasser Recursion 21

 Runtime??
Example of Linear Recursion
Recursion trace of linearSum(data, 5)
Algorithm linearSum(A, n): called on array data = [4, 3, 6, 2, 8]
Input:
Array, A, of integers
Integer n such that
0 ≤ n ≤ |A|
Output:
Sum of the first n
integers in A

if n = 0 then
return 0
else
return
linearSum(A, n - 1) + A[n - 1]

© 2014 Goodrich, Tamassia, Goldwasser Recursion 22