Java
TOPIC 05 – RECURSION
AP EXTRA

AP LESSON WORK

QUESTION 1

a) Choose one of the following famous recursion scenarios:

· Triangular numbers

· Factorial

· Fibonacci numbers

b) Implement a solution to your choice without using recursion.

c) Implement a solution to your choice using recursion.

QUESTION 2

Consider the following scenario. Mario needs to get across to the 12^th block on the right. At any point, he can either jump one block over or jump two blocks over.

You want to calculate how many different ways Mario could cross the blocks without going backwards.

a) Let W_n represent the number of ways that Mario can cross over n blocks.

Start by considering this problem if there were only two blocks. How many ways could Mario cross? So, what is W₂ equal to?

b) What about three block? What is W₃ equal to?

c) Four blocks? W₄?

d) Can you come up with a general equation for W_n that works for more than four blocks? Hint: It will be recursive!