CODEWITHSUNDEEP
cpointersrecursion
user4058730
user4058730

Reputation:

Pointers in C with recursion

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;
}

Upvotes: 3

Views: 11069

Answers (4)

AnT stands with Russia
AnT stands with Russia

Reputation: 320777

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.

Upvotes: 6

John C
John C

Reputation: 1981

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.

Upvotes: 1

ICTylor
ICTylor

Reputation: 470

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

Upvotes: 3

Peter R
Peter R

Reputation: 414

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;
}

Upvotes: 1

Related Questions