Java
TOPIC 05 – FUNCTIONS REVIEW

AP EXTRA

AP LESSON NOTE

FAMOUS RECURSION CASES

We will look at a few famous recursion scenarios.

TRIANGULAR NUMBERS

Let T_n be the number of dots in the n^th triangular number.

Recursive definition: T_n = n + T_n-1
Base case: T₁ =1

FACTORIAL

The exclamation mark is read ‘factorial’.

Recursive definition: n! = n x (n-1)!

Base case: 1! = 1

FIBONACCI SEQUENCE

Consider the following famous Fibonacci sequence where a number is the sum of its two predecessors:

Let fib(n) be the value of the n^th number in the sequence. So, fib(6) is 8.

Recursive definition: fib(n) = fib(n-1) + fib(n-2)

Base cases: fib(1)=1 and fib(2)=1