Luca Muscolo Luca Muscolo - 3 months ago 15
C Question

Need to know why the code behaves in this way - explanation code in C

#include <stdio.h>

int main() {
int c;

c = f(3, 5);
printf("c = %d\n", c);
c = f(4, 2);
printf("c = %d\n", c);
c = f(2, 4);
printf("c = %d\n", c);
c = f(3, 3);
printf("c = %d\n", c);
}

int f(int d, int e) {
if (e > 0)
return f(d, e - 1) + f(d, e - 1);
else
return d;
}


I know the code gives me the product between
d
(the first number in
f
) and
2
elevated to the second number in f(function)

The problem is that I don't understand why it gives me such output, I don't see any operators within the code (something like an equation d*2^e).
An a deep explanation would be very appreciated, feel free to recommend any material which can be helpful in learning C.

Answer

This is a simple recursive function, I can write in such way:

         |  f(d, e-1) + f(d, e-1)   if e > 0
f(d,e) = |
         |  d                       otherwise

But I can simply add two equal terms f(d,e-1), and then it becomes:

         |  2* f(d, e-1)    if e > 0
f(d,e) = |
         |  d               otherwise

In order to let you understand, just try to expand the function. Following the rule, I can write:

f(d,0) = d    for all d  // Identify function

That because the definition, since e=0.

Going ahead:

f(d, 1) = 2*f(d, 0) =           2*d

f(d, 2) = 2*f(d, 1) = 2*(2*d) = 4*d

f(d, 3) = 2*f(d, 2) = 2*(4*d) = 8*d

...  // Inductivly...
f(d, k) =  2^k *d     // for k > 0