The following definitions:

def inc(n: Int) = n + 1 def dec(n: Int) = n 1 def isZero(n: Int) = n == 0

In the following problems, your solutions may assume that all inputs are non-negative integers (these are sometimes called the natural numbers).

Problem 1

Find classical and tail recursive implementations of the Fibonacci function. I.e. fib(n) = n^th Fibonacci number.

Problem 2

Find a recursive implementation of:

choose(n, m) = # of ways to choose m things from n

Note: n and m are non-negative integers.

Hint: Pick a special item from the set. Call it x. Then add the number of choices containing x and the number that don't.