Introduction to Java Programming and Data
Structures
Thirteenth Edition
Chapter 18
Recursion
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Problem Solving Using Recursion (1 of 2)
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
subproblems recursively. A subproblem is almost the same
as the original problem in nature with a smaller size.
Characteristics of Recursion
• All recursive methods have the following characteristics:
– The method is implemented using a conditional
statement that leads to different cases.
– 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.
Computing Factorial (1 of 11)
Mathematic notation:
n! = n * (n-1)!, n > 0
0! = 1
Function:
factorial(0) = 1;
factorial(n) = n*factorial(n-1); n > 0
ComputeFactorial
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (2 of 11)
factorial(0) 1;
factorial(n) n*factorial(n 1);
factorial(4)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (3 of 11)
factorial(0) 1;
factorial(n) n*factorial(n 1);
factorial(4) 4 * factorial(3)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (4 of 11)
factorial(0) 1;
factorial(n) n*factorial(n 1);
factorial(4) 4 * factorial(3)
4 * 3 * factorial(2))
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (5 of 11)
factorial(0) 1;
factorial(n) n*factorial(n 1);
factorial(4) 4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * (2 * factorial(1))
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (6 of 11)
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)))
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (7 of 11)
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)))
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (8 of 11)
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)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (9 of 11)
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
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (10 of 11)
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)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Computing Factorial (11 of 11)
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
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (1 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (2 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (3 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (4 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (5 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (6 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (7 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (8 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (9 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (10 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Trace Recursive Factorial (11 of 11)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
factorial(4) Stack Trace
5 Space Required
for factorial(0)
4 Space Required Space Required
for factorial(1) for factorial(1)
3 Space Required Space Required Space Required
for factorial(2) for factorial(2) for factorial(2)
2 Space Required Space Required Space Required Space Required
for factorial(3) for factorial(3) for factorial(3) for factorial(3)
1 Space Required Space Required Space Required Space Required Space Required
for factorial(4) for factorial(4) for factorial(4) for factorial(4) 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)
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
Copyright © 2024 Pearson Education, Inc. All Rights Reserved
