Practical Coding in Java

Coding Exercises: Recursion

Recursive sum

Write a recursive function that takes a single integer n as input and returns the sum of integers from 1 to n. Notice that this is very similar to the factorial function.

int sum(int n);

sum(1) -> 1
sum(2) -> 1+2 == 3
sum(3) -> 1+2+3 == 6
sum(4) -> 1+2+3+4 == 10

Geometric sequence

Pick a geometric sequence (e.g. 2, 6, 18, 54, …) Write a recursive function that takes a single integer n as input and returns the nth term in the geometric sequence.

Fibonacci

Write a recursive function that takes a single integer n as input, and returns the nth Fibonacci number.

Binomial coefficients

Let \(C(n,k)\) be the number of combinations of \(n\) items taken \(k\) at a time.

\(C(n,k)\), also denoted \(\binom{n}{k}\), is defined by: \[ C(n,k) = \dfrac{n!}{k!(n-k)!} \]

The numbers \(C(n,k)\) appear in the expansion of nth powers of binomials, and so they are sometimes called binomial coefficients. These are also the numbers that appear in Pascal’s Triangle.

The binomial coefficients satisfy a recursive relation: \[ C(n,k) = C(n-1,k-1) + C(n-1,k) \]

Calculate the binomial coefficients recursively using this recursion relation.

Binomial search

Implement binary search with a recursive function.

Merge sort

Implement merge sort using recursion.