Overview / Logistics

A recursive function is a function that calls itself as it's evaluating a particular input. The purpose of this exercise is to get students practice seeing how recursive functions are evaluated. In particular, students will write code to show the process.

Problem 1

Consider the following recursive function

\[ g(x) = \left\{ \begin{array}{cc} 2g(x-3) + 1 & x > 0 \\ 3x & \text{otherwise} \end{array} \right\} \]

This can be written in python as

If you go to evaluate g(8), the following calls will be made

That is, g(8) requires g(5), which requires g(2), which requires g(-1). At g(-1), we hit a stopping condition, where the recursion no longer continues. At that point, we can start to substitute things in back up the chain.

Your task in this exercise is to modify the python code to print the above code. Every time you go one deeper into the recursion, you should print two more spaces. For example, if you have a variable depth storing how deep you are with recursive calls, you can use code like this to print the stopping condition

Problem 2

Consider the following recursive function

\[ h(x) = \left\{ \begin{array}{cc} h(x-15)+1 & x > 5 \\ x & 0 \leq x \leq 5 \\ h(x+3) & x < 0 \end{array} \right\} \]

Write out code to print the recursive calls, test it with a few numbers, and make sure your answer makes sense

Problem 3

Consider the following recursive function

\[ A(m, n) = \left\{ \begin{array}{cc} n+1 & m=0 \\ A(m-1, 1) & n = 0 \\ A(m-1, A(m, n-1)) & \text{otherwise} \end{array} \right\} \]

This one is a little more complicated than some of the above examples, because the second argument in the third case is itself a recursive call. So you should print a little more information to help you trace through it. Below is an example

What happens when you do A(3, 3)? What about A(3, 4)? What about A(4, 3)?