Recursion

Recursion Exercises

General instructions: Do NOT use global variables in any of the following functions. Also, try to use as few number of local variables as possible.

In some cases, I have explicitly stated that you should write both tail recursive as well as non-tail recursive version. In all other cases, you need to implement only one solution - either tail recursive or non-tail recursive (whatever comes naturally to you).

a) Write a recursive function called "show" which works like this:

       show(a, b)

This will print all numbers from a to b (assume a is less than b).

Draw the recursion diagram for "show(2,6)". Is your function tail recursive or non-tail recursive?

b) Write a recursive function called "sum_series" which works like this:

      sum_series(5, 10)

This will return sum of all numbers from 5 to 10. In general, sum_series(a, b) returns a+(a+1)+(a+2)+..+b.

Draw the recursion diagram.

Implement both non-tail recursive as well as tail-recursive solutions for the above problem. For implementing the tail recursive version, you may have to change the number of parameters to sum_series (think about the way we implemented tail recursive factorial).

c) Write tail-recursive as well as non-tail recursive versions of a function called "sum_digits" which will compute sum of digits of its argument. For example, given the number 123, sum_digits should return 6 (that is, 1+2+3).

Draw the recursion diagrams for both versions.

d) Write tail recursive as well as non-tail recursive version of the "power" function which computes "a raised to b". Assume "a" and "b" are positive integers; "b" may be zero.

Draw the recursion diagrams for both versions.

e) Write an optimized version of the "power" function which utilizes the idea that given the number say a^3, you can find out a^6 by a simple squaring operation (rather than multiplying with "a" 3 times).

f) Write a recursive function which will print a number (given as its argument) in binary.

g) Write an optimized version of the fibonacci number function using the idea discussed in class (ie, store computed values in an array - don't compute them again). Compare the performance of the optimized and non-optimized versions.