How it prints 140......

Question

I can't understand how it prints 140 in output, can anyone explain to me...
https://code.sololearn.com/cQNx4dhX634z/?ref=app

Answer 1

#include <stdio.h>

int fun(int a,int b){
if(b==0){
return 0;
}
if(b%2==0){
return fun(a+a,b/2);
}
return fun(a+a,b/2)+a;
}

int main() {
printf ("%d",fun(7,20));
return 0;
}
This work in this way
F(7,20)->f(14,10)->f(28,5)->28+(f(56,2)->f(112,1)->112+(f(224,0)))

28 +112+0=140

Answer 2

Important to understand the result is the part where the value of a is added to the result of the next recursive call.

Here the recursion splitted into steps:

1) a = 7, b = 20
2) a = 14, b = 10
3) a = 28, b = 5
4) result = 28, a = 56, b = 2
5) a = 112, b = 1
6) result = 140 (28 + 112), a = 224, b = 0
7) no further call

Answer 3

Let's pass the smaller numbers to it like fun(2, 3).

It simulates the multiplication. We know 4*3 = 12, and we also know 4*3 means 4+4+4(add 4 three times). That is what fun() does. You may notice that 3 is divide by two and 4 is multiply by two in both conditions. This is because addition like 2+2+2+2 can be simplify to 4+4. What about 4+4+4 I mentioned? Because 3 divide by half is 1 in C. Clearly 8 != 4+4+4. So it added an extra 4 after fun(2, 3) and become 8+4.

fun(4, 3) -> fun(4, 1) + 4 -> fun(8, 0) + 8 + 4 -> 0 + 8 + 4 = 12