Recursion

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 1
What is Recursion
⚫ Recursion is a technique by which a method makes one or
more calls to itself during execution.
⚫ Recursion is a technique that leads to elegant solutions to
problems that are difficult to program using simple loops.
⚫ A recursive method can call itself either directly or
indirectly through another method.
What is Recursion
⚫ Recursion
⚫ When a method calls itself

⚫ Classical example – the factorial function

⚫ n! = 1· 2· 3· ··· · (n-1)· n

⚫ Recursive definition
 1 if n = 0
f ( n) = 
n  f (n − 1) else
 Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);

n! = n * (n-1)!

ComputeFactorial Run

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 4
 Computing Factorial

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 5
animation

Computing Factorial
factorial(0) = 1;
factorial(n) = n*factorial(n-1);
factorial(4) = 4 * factorial(3)
= 4 * 3 * factorial(2)
= 4 * 3 * (2 * factorial(1))
= 4 * 3 * ( 2 * (1 * factorial(0)))
= 4 * 3 * ( 2 * ( 1 * 1)))
= 4 * 3 * ( 2 * 1)
=4*3*2
=4*6
= 24
Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 6
 animation

Trace Recursive factorial

returns factorial(4)

factorial(4)
Step 0: executes factorial(4)
Step 9: return 24
return 4 * factorial(3)
Step 1: executes factorial(3)
Step 8: return 6
return 3 * factorial(2)
Step 2: executes factorial(2)
Step 7: return 2
return 2 * factorial(1)
Step 3: executes factorial(1)
Step 6: return 1
return 1 * factorial(0)
Step 4: executes factorial(0)
Step 5: return 1
return 1

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 7
 factorial(4) Stack Trace
5 Space Required
for factorial(0)

4 Space Required
for factorial(1)
Space Required
for factorial(1)

3 Space Required
for factorial(2)
Space Required
for factorial(2)
Space Required
for factorial(2)

2 Space Required
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(3)
Space Required
for factorial(3)

1 Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)
Space Required
for factorial(4)

6 Space Required
for factorial(1)
Space Required 7 Space Required
for factorial(2) for factorial(2)
Space Required Space Required 8 Space Required
for factorial(3) for factorial(3) for factorial(3)
Space Required Space Required Space Required 9 Space Required
for factorial(4) for factorial(4) for factorial(4) for factorial(4)

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 8
What is the difference between
these two methods?

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 9
Output of the following programs

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 10
 Fibonacci Numbers
Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89…
indices: 0 1 2 3 4 5 6 7 8 9 10 11

fib(0) = 0;
fib(1) = 1;
fib(index) = fib(index -1) + fib(index -2); index >=2

fib(3) = fib(2) + fib(1) = (fib(1) + fib(0)) + fib(1) = (1 + 0)

+fib(1) = 1 + fib(1) = 1 + 1 = 2

ComputeFibonacci Run
Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 11
 Fibonnaci Numbers, cont.
fib(4)
17: return fib(4) 0: call fib(4)

return fib(3) + fib(2)

11: call fib(2)
10: return fib(3)

1: call fib(3) 16: return fib(2)

return fib(2) + fib(1) return fib(1) + fib(0)

7: return fib(2) 8: call fib(1) 14: return fib(0)
2: call fib(2) 13: return fib(1) 12: call fib(1)

9: return fib(1) 15: return fib(0)

return fib(1) + fib(0) return 1 return 1 return 0
4: return fib(1) 5: call fib(0)

3: call fib(1)

return 1 6: return fib(0) return 0

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 12
 Characteristics of Recursion
All recursive methods have the following characteristics:

– One or more base cases (the simplest case) are used to stop
recursion.
– Every recursive call reduces the original problem, bringing it
increasingly closer to a base case until it becomes that case.

In general, to solve a problem using recursion, you break it

into subproblems. If a subproblem resembles the original
problem, you can apply the same approach to solve the
subproblem recursively. This subproblem is almost the
same as the original problem in nature with a smaller size.

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 13
 Problem Solving Using Recursion
nPrintln(“Welcome“, 5);
1. one is to print the message one time and the other is to
print the message for n-1 times.
2. The second problem is the same as the original problem
with a smaller size.
3. The base case for the problem is n==0. You can solve
this problem using recursion as follows:
public static void nPrintln(String message, int times) {
if (times >= 1) {
[Link](message);
nPrintln(message, times - 1);
} // The base case is times == 0
}

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 14
 Recursive Selection Sort
1. Find the smallest number in the list and swaps it
with the first number.
2. Ignore the first number and sort the remaining
smaller list recursively.

RecursiveSelectionSort

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 15
 Recursive Selection Sort

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 16
 Recursive Binary Search
1. Case 1: If the key is less than the middle element,
recursively search the key in the first half of the array.
2. Case 2: If the key is equal to the middle element, the
search ends with a match.
3. Case 3: If the key is greater than the middle element,
recursively search the key in the second half of the
array.

RecursiveBinarySearch

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 17
 Recursive Binary Search

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 18
Tower of Hanoi, cont.
▪There are n disks labeled 1, 2, 3, . . ., n, and three towers labeled A, B, and C.
▪No disk can be on top of a smaller disk at any time.
▪All the disks are initially placed on tower A.
▪Only one disk can be moved at a time, and it must be the top disk on the tower.

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 19
 Solution to Tower of Hanoi
The Tower of Hanoi problem can be decomposed into three
subproblems.

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 20
 Solution to Tower of Hanoi

❑ Move the first n - 1 disks from A to C with the assistance of tower

B.
❑ Move disk n from A to B.
❑ Move n - 1 disks from C to B with the assistance of tower A.

TowerOfHanoi Run
Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 21
Solution to Tower of Hanoi

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 22
 Tail Recursion
A recursive method is said to be tail recursive if
there are no pending operations to be performed on
return from a recursive call.

Non-tail recursive

Tail recursive

Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 23
 Disadvantage of Recursion
Recursion is an alternative form of program
control. It is essentially repetition without a loop.

Recursion bears substantial overhead. Each time

the program calls a method, the system must assign
space for all of the method’s local variables and
parameters. This can consume considerable
memory and requires extra time to manage the
additional space.
Recursive programs can run out of memory,
causing a StackOverflowError
Liang, Introduction to Java Programming, Tenth Edition, Global Edition. © Pearson Education Limited 2015 24