Value returned by recursive function

Question

(pseudocode)

f(x,y,z) 
{
    if (x < y) 
    {
        return 1 + f(x + 1, y, z)
    } 
    else if (y < z) 
    {
        return 2 + f(x, y + 1, z)
    } 
    else 
    {
        return z
    }
}

The function call f(12,14,20) returns $40$. Why is this the case? As the final statement is return z, should it not simply return $20$, which would be the value of $z$ at which the recursion stops - $(20,20,20)$?

How does one go about analysing such a function?

Answer 1

Here's what goes on; there are three different cases:

1. If $x<y$, you pass from $(x,y,z)$ to $(x+1, y, z)$ and add 1 to the eventually returned result.
2. If $x\ge y$ and $y<z$, you pass from $(x,y,z)$ to $(x,y+1, z)$ and add 2 to the result.
3. If $x\ge y$ and $y\ge z$ you return z (plus all the additions you made in cases (1) and (2).

Suppose, for simplicity's sake, we start with $(2,4,6)$. First, we're in case (1), so we pass from $(2,4,6)$ to $(3,4,6)$ and add 1. We then pass to $(4,4,6)$, adding another 1 and pass to case (2). In general, we'll add $1\cdot(y-x)$ in this case.

Now we alternate between case (2) and case (1). In this example, we'll go from $(4,4,6)$ to $(4, 5,6)$ (case 2) and add 2 and then from $(4,5,6)$ (case 1), add 1, and go to $(5,5,6)$, so we've gone from $(4,4,6)$ to $(5,5,6)$ and added 3. Another case (2), case (1) will get us to $(6,6,6)$ In general, we'll add $3\cdot(z-y)$ in this case.

Finally, we arrive at $(6,6,6)$ and find ourselves in case (3) where we return 6 plus the adds we made earlier, namely 2 to get from $(2,4,6)$ to $(4,4,6)$, 6 more to get from $(4,4,6)$ to $(6,6,6)$ for a grand total of $f(2,4,6)=2+6+6=14$.

In general, when $x\le y\le z$ we'll have $$ f(x,y,z)=1\cdot(y-x)+3\cdot(z-y)+z=4z-2y-x $$

It's not hard to establish similar results in the cases where $x,y,z$ aren't sorted in increasing order.

[By the way, $f(12,14,20)=4\cdot20-2\cdot14-12=80-28-12=40$.]

Answer 2

D.W. has included a general method for tracing recursive calls in a code, in his answer. Or as Rick Decker has pointed you can also try to solve the recurrence relation. Adding to what they have explained, I would like to point that while tracing or keeping track of the recursive calls in general you may want to take the aid of stacks ( that is how recursion is implemented in programming languages ). I will try to show how it helps in your example.

( 20 20 20 ) | 20  |
( 19 20 20 ) |  1  |
( 19 19 20 ) |  2  |
( 18 19 20 ) |  1  |
( 18 18 20 ) |  2  |
( 17 18 20 ) |  1  |
( 17 17 20 ) |  2  |
( 16 17 20 ) |  1  |
( 16 16 20 ) |  2  |
( 15 16 20 ) |  1  |
( 15 15 20 ) |  2  |
( 14 15 20 ) |  1  |
( 14 14 20 ) |  2  |
( 13 14 20 ) |  1  |
( 12 14 20 ) |  1  |


(x,y,z)      | value to be added while returning |

In the above figure, the stack grows from bottom to top. The left hand side represents the x,y,z triplet, that is the arguments of the recursive calls. The right hand side is the stack in the figure. It's elements are what you have to add to the answer you get from the next recursive call . I might not be able to put it in good language. An example might help. Initially you are at the bottom 12,14,20, from here you call the function again with arguments 13,14,20. Once you have an answer from 13,14,20 you will add 1 ( because you are doing 1 + f(13,14,20) ) to whatever you received from the call with arguments 13,14,20 and return it. Thus you push 1 into the stack. Likewise the stack is build from bottom to top. Once the call 20,20,20 you have to return value 20 ( that is the value of z, the else part of the code ) to the previous recursive call. From this point onward just start popping the stack , and when you pop an element add it to the element which is now at the top. This way you will get answer to be 40 in the end.

Answer 3

Here's one way to go about analysing this situation: "run" the code by hand, one step at a time. Build a table where you predict what the value of each variable will be at each step of execution. Then, run the program in a debugger and see what the actual values are at each step. Use this to identify the first step where your predictions don't match the actual values.

This will let you identify a single statement in the code that you don't understand: a single statement where you know the value of all variables before executing that statement, and where you know the value afterwards, and where your prediction for the value afterwards doesn't match the actual values. This lets you narrow down exactly where you went wrong. Often, once you've done that, it will become easier to see or hypothesize what might be wrong with your understand.

With this approach, you can construct a "minimal working example": a minimal program that behaves differently from what you'd expect. Your minimal working example will be a three-line program, where the first line sets the value of all the variables, the second line is the single line you identified above, and the third line prints out the value of one of the variables. Identifying a minimal working example is a key debugging skill.

(To elaborate, when I talk about "running" the code by hand one step at a time, here's what I mean. This means tracing through through the sequence of recursive calls one-by-one, and tracing through the execution of each line of code one line at a time.)