Write a recursive function named fibonacci that accepts an integer n as a parameter and returns the nth number in the Fibonacci sequence.
The Fibonacci sequence is a sequence of numbers in which the first two numbers are 1 and each subsequent number is the sum of the previous two Fibonacci numbers.
The sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on.
Below is a correct, but inefficient, function to compute the nth Fibonacci number.
The code shown runs very slowly for even relatively small values of n; it can take minutes or hours to compute even the 40th or 50th Fibonacci number.
The code is inefficient because it makes too many recursive calls.
It ends up recomputing each Fibonacci number many times.
Write a new version of this function that is still recursive and has the same header but is more efficient.
Do this by creating a helper function that accepts additional parameters, such as previous Fibonacci numbers, that you can carry through and modify during each recursive call.
Do not use loops or auxiliary data structures; solve the problem recursively.
