3

I usually program in java and recently watching some c codes. I came up across this program and I don't know how this pointer thing is working. I know pointer stores the address and all but couldn't make it through the program. Please tell how is the output coming as 8 ?

#include <stdio.h>

int fun(int n, int * f_p) {
    int t, f;
    if (n <= 1) {
      *f_p = 1;
      return 1;
    }
    t = fun(n - 1, f_p);
    f = t + *f_p;
    *f_p = t;
    return f;
}

int main() {
    int x = 15;
    printf("%d\n", fun(5, &x));
    return 0;
}
Improve this question
10
  • 8
    Run it under a debugger and single-step through the recursion. Commented Oct 9, 2014 at 20:12
  • 8
    This is just horrible Commented Oct 9, 2014 at 20:16
  • 2
    @philippe lhardy: When you write a recursive function that needs large amounts of intermediate temporary data that does not need to be preserved as a local context and/or over the nested recursive call, then this is actually how you should do it. Create a "global" context in the caller and pass it to all recursive levels through a pointer parameter. That way all recursive levels will use the same "global" data, instead of instantiating that data locally again and again on each level of recursion. This technique will allow you to reduce stack usage and avoid stack overflow. Commented Oct 9, 2014 at 20:32
  • 1
    However, in this case it is used for a different purpose: to return a second value from the lower level to upper level. So it is not really a "context" per se. There's was no real need to use the same x variable at all levels of recursion. Commented Oct 9, 2014 at 20:33
  • 1
    @AndreyT i agree with your both comments. i nethertheless stick to the fact that two lines of comments in the code would perhaps have saved a SO post :-). Commented Oct 9, 2014 at 20:36

4 Answers 4

Reset to default
6

What you have here is a recursive function that calculates the i-th element of a Fibonacci sequence (indexing from 0). Each recursive iteration returns two values: the i-th Fibonacci number and the (i-1)-th (previous) Fibonacci number. Since a function in C can only return one value (well, unless you use a struct as return type), the other value - the previous Fibonacci number - is returned to the caller through a pointer parameter f_p.

So, when you call fun(5, &x), the function will return 8, which is the 5-th Fibonacci number, and it will also place 5 into x, which is the previous (4-th) Fibonacci number.

Note that the initial value of x does not matter. That 15 does not play any role in this program. Apparently it is there as a red herring.

If you know what a Fibonacci sequence is, you know that the next element of the sequence is the sum of the two previous elements. This is why the function is written to "return" two elements of the sequence to the caller. You might not care about that previous value in the top-level caller (i.e in main), but the nested recursive calls do need it to calculate the next number. The rest is pretty straightforward.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

3

Step by step:

  1. fun gets called with a 5 and the x address
  2. fun calls fun with a 4 and f_p, which is the x address
  3. fun calls fun with a 3 and f_p, which is the x address
  4. fun calls fun with a 2 and f_p, which is the x address
  5. fun calls fun with a 1 and f_p, which is the x address
  6. fun got called with a 1 so the if condition is true, puts a 1 in the variable pointed by f_p(x) and returns 1
  7. this returned value is assigned to the t of the fun(2,f_p), f is f = t + *f_p which is 1+1 -> f=2; the variable pointed by f_p is set to t so x=1, returns f so it returns 2
  8. this returned value is assigned to the t of the fun(3,f_p), f is f = t + *f_p which is 2+1 -> f=3; the variable pointed by f_p is set to t so x=2, returns f so it returns 3
  9. this returned value is assigned to the t of the fun(4,f_p), f is f = t + *f_p which is 3+2 -> f=5; the variable pointed by f_p is set to t so x=3, returns f so it returns 5
  10. this returned value is assigned to the t of the fun(5,f_p)(the first call to fun), f is f = t + *f_p which is 5+3 -> f=8; the variable pointed by f_p is set to t so x=5, returns f so it returns 8, which is what the printf prints
Improve this answer

Comments

1

Another answer revealed this to calculate the fibonacci numbers using a useful technique for returning an extra value. I've rewritten the code in what I think is a much more understandable and maintainable manner. Hope this prevents people thinking you need to write terrible code to do something like this

#include <stdio.h>

int fib(int n) {
    // This is used to return the previous fib value
    // i.e. fib(n - 1)
    int prevValRet;
    return fibRec(n, &prevValRet);
}

// *prevValRet contains fib(n-2)
int fibRec(int n, int *prevValRet) {
    // Termination case
    if (n <= 1) {
      // return fib(0) and fib(1) as 1
      *prevValRet = 1;
      return 1;
    }
    // Calculate fib(n-1)
    int prevVal = fibRec(n - 1, prevValRet);
    // Calculate fib(n) = fib(n-1) + fib(n-2)
    int thisVal = prevVal + *prevValRet;
    // Return fib(n-1) and fib(n)
    *prevValRet = prevVal;
    return thisVal;
}

int main() {
    printf("%d\n", fib(5));
    return 0;
}
Improve this answer

Comments

1

As these things go, it's technically straightforward, but...stupid, in the sense that nobody should do things like this. It's a bad use of recursion and badly-written recursion, given the side effects.

The original call of fun(5, &x) isn't going to trip the condition. So, it'll recurse four times (5-1, 4-1, 3-1, 2-1). That's your base condition, which has the effect of setting the pointed-to location (the original x) to 1 and returning 1.

Then we unroll the four calls, each time adding the returned value to the thing at the pointer and changing the thing at the pointer to be that sum.

In simple English, you're doubling one three times.

Edit: As pointed out, I misread the code as assigning f to *f_p rather than t. That makes it a Fibonacci counter.

Improve this answer

4 Comments

What is "you're doubling one three times" intended to mean?
It calculates fibonacci, there is no doubling - it will add 1 + 1 = 2 then 1 + 2 etc
@PeterR, you're right. I zoned on the t and f. Yet more evidence of bad code.
@AndreyT, a mis-read of *f_p = t; as *f_p = f;. That would return 1, then double it three times by adding the value to itself then storing it at the pointer.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.