Pointers in C with Recursion
I usually program in java and have been looking at some c codes recently. I have applied this program and I do not know how this pointer works. I know the pointer stores the address and that's it, but couldn't execute it through the program. Please tell me how is output 8 displayed?
#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;
}
Here you have a recursive function that calculates the i-th element of the 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 from C can only return one value (well, unless you use struct as its return type), another value - the previous Fibonacci number - is returned to the caller via a pointer parameter f_p
.
So when you call fun(5, &x)
, the function will return 8
which is the 5th Fibonacci number and it will also put 5
in x
which is the previous (4th) Fibonacci number.
Please note that the initial value x
is irrelevant. It 15
does not play any role in this program. Apparently there is a red herring there.
If you know what a Fibonacci sequence is, you know that the next element in the sequence is the sum of the two previous elements. This is why the function is written to "return" two sequence elements to the caller. You may not like this previous value in the top-level caller (that is, in main
), but nested recursive calls need it to calculate the next number. The rest is pretty simple.
source to share
How it all happens is technically straightforward, but ... stupid in the sense that no one should do that. This is a bad use of recursion and poorly written recursion considering the side effects.
The original call fun(5, &x)
will not disable the condition. Thus, it will run four times (5-1, 4-1, 3-1, 2-1). This is your baseline condition that affects setting the sharpened location (original x
) on 1
and back 1
.
We then expand the four calls, each time adding the return value to the item in the pointer and changing the item in the pointer to be that amount.
In plain English, you double three times.
Edit . As stated, I am wrongly reading the code as assignment f
<<25>, not t
. This makes it a Fibonacci counter.
source to share
Another answer showed this to calculate Fibonacci numbers using a useful technique to return additional value. I rewrote the code in what, in my opinion, is much clearer and more convenient. Hopefully this prevents people from thinking that you have to write scary 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;
}
source to share
Step by step:
- fun is called with 5 and address x
- fun is fun with 4 and f_p , which is the x address
- fun is fun with 3 and f_p , which is the x address
- fun is fun with 2 and f_p which is the address of x
- fun is fun with 1 and f_p , which is the x address
- fun got called with 1, so the if condition is true, puts 1 in the variable denoted by f_p (x) and returns 1
- this return value is assigned to t fun (2, f_p) , f
f = t + *f_p
, which is 1 + 1 → f = 2; the variable pointed to by f_p is set to t so x = 1, returns f, so it returns 2 - this return value is assigned to t fun (3, f_p) , f is
f = t + *f_p
, which is 2 + 1 → f = 3; the variable pointed to by f_p is set to t so that x = 2, returns f, so it returns 3 - this return value is assigned to t fun (4, f_p) , f
f = t + *f_p
, which is 3 + 2 → f = 5; the variable pointed to by f_p is set to t so x = 3, returns f, so it returns 5 - this return value is assigned to t fun (5, f_p) (first call for fun), f -
f = t + *f_p
which is 5+ 3 → f = 8; the variable pointed to by f_p is set to t, so x = 5, returns f, so it returns 8 , which is what printf prints
source to share