easy way to do recursion on paper?

Question

I am preparing for computer science AP exam and have recursions as one of the topics. Being reletively new to programming I wanted to know if there is any easy way, or a few tips you would like to offer regarding recursion. On the exam we have no access to the computer (obviously). So what is an easy way to find solutions to recursions. For example the following is a problem diectly from my book.

public static int mystrey(int x)
{
    if(x == 0)
    {
        return 0;
    } 
    else
    {
        return (x + mystrey(x/10)+mystrey(x/4);
    }
} 

What would be the return value if mystrey(10) is called?

Answer 1

Well if you use recursion it's good to know the meaning of the function. This helps a lot to understand why the method is recursive. Furthermore calculating the function on paper is mostly done by a method called "dispatching". In this case you see that mystrey(0) = 0 (the if-case).

If you want to calculate the value of mystrey(10) you know it's a sum of 10, mystrey(1) and mystrey(2).

You simply create a table where one can put:

0: 0
10: 10+f(1)+f(2)

we now calculate the value of the function with the highest argument so mystrey(2):

2: 2+f(0)+f(0)

we know the value of f(0), it's already in the table, so

2: 2+0+0=2

now we calculate f(1)=1

We finally conclude that f(10)=10+f(1)+f(2)=10+1+2=13.

Using a table becomes helpfull when there is a lot of recursion. A lot of times recursion results in overlap, where a huge number of times the function with the same arguments must be computed. With dispatching one can avoid the "branching". One can see recursion as a tree. Because f(0) has a fixed value this is called the "base case" and are the leafs of the tree. The other function values are called "branches". When calculating f(10) we need to calculate f(1) and f(2), so one could draw edges from f(10) to f(2) and f(1). And so one could repeat the process.

Also in most cases a good programmer will program this dispatching in the algorithm. This is of course done by declaring an array an store values in the array and perform a lookup on it.

In recursion theory it's common the recursion consist of two parts: a base case part, where answers are "hard coded" for some function calls (in your example when x=0), and a recursive part where f(x) is written in parts of f(y). In general one can use dispatching by building an intial table with the hard coded values, and calculate the value of a specific x by starting to fill in the entry of x in the table, and work down.

Answer 2

Recursion is a pain to unroll manually. Basically, you substitute each recursive call with its output:

  mystrey(10)
= 10 + mystrey(10/10) + mystrey(10/4)
= 10 + (1 + mystrey(1/10) + mystrey(1/4)) + (5/2 + mystrey(5/20) + mystrey(5/8))
= ...

Since you declared the variables to be int types, everything smaller than 1 is mapped to 0. Your if (x == 0) case returns 0 if x == 0, so you can conclude:

  mystrey(10)
= 10 + (1 + mystrey(1/10) + mystrey(1/4)) + (5/2 + mystrey(5/20) + mystrey(5/8))
= 10 + (1 + mystrey(0) + mystrey(0)) + (5/2 + mystrey(0) + mystrey(0))
= 10 + (1 + 0 + 0) + (5/2 + 0 + 0)
= 11 + 5/2

5/2 is evaluated to 2, so your final answer is 13 (I checked by running your code in Python).