What three things does a correct recursive method need?
Compare with the model answer
A branch that separates cases; at least one recursive call on a smaller version of the problem; and a base case that stops without recursing.
Recursion
Recursive methods, base cases and recursive cases, countdown, the call sequence, infinite recursion and stack overflow, recursion vs. iteration, tail recursion, factorial, Fibonacci, and a recursive power method.
How to read this page
Every original slide is shown unchanged. Yellow marks on a slide point to a numbered note: hover or tap a mark to jump to its note, and hover a note to see its marks. Questions tagged Past exam appeared on a real paper; Prediction questions are likely angles, not confirmed. Pick an answer to each question: a wrong pick tells you why it is wrong, so you can try again.
All 30 slides
- 1 Recursion
- 2 Objectives
- 3 Basics of Recursion
- 4 Simple Example - Countdown
- 5 Recursive Countdown
- 6 See code for count down
- 7 Sequence of Calls
- 8 Keys to Successful Recursion
- 9 Infinite Recursion
- 10 Recursive Versus Iterative
- 11 Recursive Versus Iterative
- 12 Recursion
- 13 Recursion
- 14 Tail Recursion
- 15 Factorial
- 16 • A recursive declaration of the factorial method is arrived at by observing the
- 17 • The evaluation of 5! would proceed as shown in Fig. 18.2.
- 18 Slide 18
- 19 The recursive method factorial (lines 7–13) first tests to
- 20 See code for factorial
- 21 Slide 21
- 22 Example Using Recursion: Fibonacci Series
- 23 18.4 Example Using Recursion: Fibonacci Series (cont.)
- 24 See code for Fibonacci
- 25 Slide 25
- 26 (Recursive power Method)
- 27 See Code for Pow
- 28 Sample output
- 29 See code
- 30 Summary
Recursion
Objectives
Basics of Recursion
Notes
A recursive method calls itself on a smaller version of the same problem.
Simple Example - Countdown
Recursive Countdown
See code for count down
Sequence of Calls
Keys to Successful Recursion
Exam angle
Infinite Recursion
Notes
No base case (or not getting smaller) → infinite recursion → StackOverflowError.
Exam angle
Infinite recursion in Java eventually causes:
Recursive Versus Iterative
Recursive Versus Iterative
Notes
Recursion uses more memory (a stack frame per call) and is often slower; but can be clearer.
Recursion
Recursion
Tail Recursion
Factorial
• A recursive declaration of the factorial method is arrived at by observing the
Notes
n! = n × (n − 1)!, with 0! = 1! = 1.
Exam angle
Write a recursive factorial method.
Compare with the model answer
public static long factorial(long n) { if (n <= 1) return 1; return n * factorial(n - 1); }
• The evaluation of 5! would proceed as shown in Fig. 18.2.
Slide 18
The recursive method factorial (lines 7–13) first tests to
See code for factorial
Slide 21
Example Using Recursion: Fibonacci Series
Notes
Fibonacci: 0, 1, 1, 2, 3, 5, 8…; fib(n) = fib(n − 1) + fib(n − 2).
Exam angle
With fib(0) = 0 and fib(1) = 1, fib(6) is:
18.4 Example Using Recursion: Fibonacci Series (cont.)
Notes
Two base cases: fib(0) = 0, fib(1) = 1. Naïve recursion repeats work exponentially.
See code for Fibonacci
Slide 25
(Recursive power Method)
Exam angle
Write a recursive power(base, exponent).
Compare with the model answer
public static int power(int base, int exponent) { if (exponent == 1) return base; return base * power(base, exponent - 1); }
See Code for Pow
Sample output
See code
Summary
