Power

Write a recursive algorithm to compute x^n. Trace through the algorithm for n = 3.

Recurrent Sequence

Let u_n be defined by u_0 = 1515 and u_(n+1) = 3*u_n + 42 for n in N*. Write a recursive algorithm to compute u_k for a given k.

Fibonacci

Let u_n be defined by u_0 = 1, u_1 = 1 and u_(n+1) = u_n + u_(n-4) for n in N*. Write a recursive algorithm to compute u_k for a given k.

Paths on a Grid

Source: projecteuler.net #15

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

Coin Partitions

Source: projecteuler.net #78

Let p(n) represent the number of different ways in which n coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so p(5)=7.

OOOOO
OOOO   O
OOO   OO
OOO   O   O
OO   OO   O
OO   O   O   O
O   O   O   O   O

Find the least value of n for which p(n) is divisible by one million.