How do recursive functions work? (C++)

Question

I'm having a very hard time grasping the concept of recursive functions in C++. I understand this sort of function calls itself repeatedly until an exit condition is met, but what puzzles me is what is the function doing until an exit condition is satisfied. For example, in the following code, if 3 is passed as the argument for 'u', the function yields 133. Why is 'u' returning that value?

int u(int a)
{
if (a == 0)
return 3;
else
return 3 * u(a -1) + 4;
}

Answer 1

Let's look at u(3);

We start with a = 3.
a != 0, so we go to the else part:
return 3 * u(a -1) + 4; -> return 3 * u(3 -1) + 4;

This calls u again, but with a = 2 this time.
a != 0, so we go to the else part:
return 3 * u(a -1) + 4; -> return 3 * u(2 -1) + 4;

This calls u again, but with a = 1 this time.
a != 0, so we go to the else part:
return 3 * u(a -1) + 4; -> return 3 * u(1 -1) + 4;

This calls u again, but with a = 0 this time.
a == 0, so we return 3;

return 3 * u(1 -1) + 4; -> return 3 * 3 + 4; (= 13)

return 3 * u(2 -1) + 4; -> return 3 * 13 + 4; (= 43)

return 3 * u(1 -1) + 4; -> return 3 * 43 + 4; (=133)

So the return value of u(3) is 133.

Answer 2

I got a decent result from this

https://code.sololearn.com/c6eiconoE3AX/?ref=app