I don't understand how this function works and how it comes to the result of 60

Question

def A(x, y):
    if x == 0:
        return y + 2
    if y == 0:
        return A(x - 1, 1) + 1
    return A(x - 1, A(x, y - 1)) * 2

print(A(1, 3))

The output is 60. I ran the code but I have no clue how you get to that value. Sorry for the rather dumb question.

Does this answer your question? [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — EJoshuaS - Stand with Ukraine, Dec 31 '19 at 17:10
add a print statement, helps with understanding. `print("Value of X: {} Value of Y: {}".format(x, y)` — Stack, Dec 31 '19 at 17:11
For this particular function, I'd suggest trying to understand recursion. https://www.freecodecamp.org/news/how-recursion-works-explained-with-flowcharts-and-a-video-de61f40cb7f9/ is a nice introduction to recursion. — Brian Minton, Dec 31 '19 at 17:18
This looks almost, but not entirely, like the [Ackermann function](https://en.wikipedia.org/wiki/Ackermann_function), so skimming that article may give you some insight on how the result is calculated for this kind of problem. — Kevin, Dec 31 '19 at 17:27
So I'am at the very beginning of my informatics course and i read the linked question plus the answer and thought I probably should shut up because I didn't use any debugger. @quamrana thannks for the question I basically don't understand how x or y even become 0 and i figured it's laughable that i don't get it — Slurm, Dec 31 '19 at 17:31

score 6 · Accepted Answer · edited Jun 20 '20 at 09:12

A appears to be recursive, so when you call A(1,3), it keeps calling itself.

Let's walk through it:

The first time you run it, x != 0, so it doesn't return y+2
y != 0, so it doesn't return A(x-1, 1) + 1
Instead, it returns A(x-1, A(x, y-1)) * 2

…

A view of this can be summarised as:

A(1,3):
    return A(x-1, A(x, y-1)) * 2
    return A(0, A(1, 2)) * 2:
        A(1,2):
            return A(x-1, A(x, y-1)) * 2
            return A(0, A(1, 1)) * 2:
                A(1,1):
                    return A(x-1, A(x, y-1)) * 2
                    return A(0, A(1, 0)) * 2:
                        A(1,0):
                            return A(x-1, 1) + 1
                            return A(0, 1) + 1:
                                A(0,1):
                                    return y+2
                                    return 3
                                3 + 1 = 4
                                return 4
                    return A(0,4) * 2:
                        A(0,4):
                            return y+2
                            return 6
                        6*2 = 12
                    return 12
            return A(0, 12) * 2:
                A(0,12):
                    return y+2
                    return 14
                14*2 = 28
            return 28
    return A(0, 28) * 2:
        A(0,28):
            return y+2
            return 30
        30 * 2 = 60
    return 60

Hopefully that 'tree' helps you visualise what is going on.

score 2 · Answer 2 · answered Dec 31 '19 at 17:42

Let's go through your program step by step:

First, we call the function A, with parameters 1, and 3.
The function A starts running and sets x to the first parameter, 1, and y to the second parameter, 3.
Execution then continues until it comes to the first if statement.
x is not 0, so we skip to the next statement, which is the second if statement.
y is not 0, so we skip to the next statement, which is the second call to the A function with the parameters x - 1 (which evaluates to 0), and A(x, y - 1) as the second parameter.
The second parameter results in a third call to A, with the parameters 1 and 2. This is computed first, then the result of it is set to the the second parameter of the second call of A
the second call to A hits the return statement, and returns the result to the first call to A. This value is then multiplied by 2, and the first call to A then returns it's value to the initial print function, which displays the number 60.

This can quickly get hard to keep track of by hand, so it's helpful to add a print statement, or use a debugger.

Here's an example of your function modified with a print statement:

def A(x, y):
    print('in A.  x:',x,'y:',y)
    if x == 0:
        return y + 2
    if y == 0:
        return A(x - 1, 1) + 1
    return A(x - 1, A(x, y - 1)) * 2

print(A(1, 3))

which produces the following output:

in A.  x: 1 y: 3
in A.  x: 1 y: 2
in A.  x: 1 y: 1
in A.  x: 1 y: 0
in A.  x: 0 y: 1
in A.  x: 0 y: 4
in A.  x: 0 y: 12
in A.  x: 0 y: 28
60

I don't understand how this function works and how it comes to the result of 60

2 Answers2