Recursion
Write the recursive function factorial(int n) that returns n! = 1*2*...*n, the
factorial of n. Assume that n is at least 0.
The function call:
factorial(0);Would produce the output:
1
factorial(5);Would produce the output:
120
The factorial function is a very fast growing function. What is the smallest number that causes an arithmetic overflow for int?
Try using a larger datatype. How much larger could this datatype handle?
Write the recursive function unsigned sum(unsigned n) that returns the sum of the first n integers i.e.
sum(n) = 1+2+...+n
The function call:
sum(0);Would produce the output:
0
sum(12);Would produce the output:
78
Part 1: The Fibonacci numbers is a series defined as follows. The first two Fibonacci numbers F_1 and F_2 are 1. The nth Fibonacci
number when n > 2 is the sum of the previous two Fibonacci numbers F_n-1 and F_n-2.
Write the recursive function int fib(int n) that returns the nth Fibonacci number. Don't forget to include
PRE and POST comments above your function header/signature.
The function call fib(1) should return 1.
fib(3) should return 2.
fib(5) should return 5.
Test your function in main() by printing out messages of the form: The 5th Fibonacci number is 5.
Part 2: Try and write an iterative version of the fib() function. The key idea is that you only need the previous two Fibonacci numbers to compute
the next one. When computing the nth Fibonacci number start by computing the first Fibonacci number, then the second Fibonacci
number, keep going until you compute the nth Fibonacci number.