Thread: HELP! What does this code do? It has recursive function in it >:(

Can someone please help me with this code? I need the detailed explanation of what does it do...I'm a bit unclear with recursive functions...

code:

Code:

 #include <stdio.h>

int f (int *a, int b) {
int c;
(a*)--;
if (b>0) c = f( &b,*a);
else return *a;
return b + c;
}

void main () {
int x;
x = 5;
printf ("%d", f(&x, 1));
}

Your teacher must have given you some kind of notation to use to figure this out. You need to keep track of the local vars (and params) of each invocation. This function is tricky because each recursive call modifies a value local to the previous call.

Show some attempt on your part and someone will help you.

Write the code down, one statement per line. Make sure you have room on the right side for annotations. (You'll need three separate columns, I think.)

Then, you start "running" the code. At line 14, you see that you have a function call, so at the start of the function call, line 4, you mark *a=x=5, b=1 as per the function call parameters. Because the first parameter is passed as a pointer, modifying *a modifies the variable used by the caller; I recommend keeping that in mind by writing it in the notes carefully. (Here, a points to x, therefore *a=x.)

On line 5, you mark *a=x=4, b=1 (in the leftmost free column), since the number pointed to by a was decreased by one.

You go on like that, line by line, marking the new variable values on the right side. When you do a function call, move to the next column on the right. Or you could use a separate strip of paper, too, I guess. Hmm.. I've never tried post-it notes, but I think those might work even better.

After a function returns, remember to note not only the return value, but also any changes the function may have done to parameters passed by reference -- i.e. here the first parameter to function f. This is the bit that trips most people, so be careful. I like to note the function parameters on the first line of the function, and the return value and modified values where the function was called, but how you do it is up to you.

If you have not done this before, I'm sure you're quite way over your head right now.

Don't worry. It is much easier to do this by adding line-numbered print statements into the program, and run it. That way the program does all the work for you. If you do this for a few programs, you'll get much better at it -- it is one of the most common ways to become a better programmer, by analyzing others' programs this way; it's a common technique even for Linux kernel programmers, who are considered quite the wizards. Eventually, it becomes just another skill, and you'll find you only need to jot down notes at complicated points like function calls.

If you were to format the code properly, and add fprintf(stderr, ...); statements showing the values of interesting variables, you might get something like this:

Code:

#include <stdio.h>
 
int f(int *a, int b)
{
	int c;

	fprintf(stderr, "Line %d: *a = %d, b = %d\n", __LINE__, *a, b);
	(*a)--;
	fprintf(stderr, "Line %d: *a = %d, b = %d\n", __LINE__, *a, b);
	if (b > 0) {
		c = f(&b, *a);
		fprintf(stderr, "Line %d: *a = %d, b = %d, c = %d\n", __LINE__, *a, b, c);
		return b + c;
	} else {
		fprintf(stderr, "Line %d: *a = %d, b = %d\n", __LINE__, *a, b);
		return *a;
	}
}

int main(void)
{
	int x, v;

	x = 5;
	fprintf(stderr, "Line %d: x = %d\n", __LINE__, x);
	v = f(&x, 1);
	fprintf(stderr, "Line %d: x = %d, v = %d\n", __LINE__, x, v);
	printf("%d\n", v);

	return 0;
}

The __LINE__ is a preprocessor macro, which expands to the line number it occurs on in the source file. Using fprintf(stderr, ...) makes these statements easy to detect, so you can add or remove them without affecting the program.

Also, if your program does printf() stuff, you can hide/discard those by running the program via ./myprog >/dev/null . That redirects all stdout stuff to "nowhere". If you use Bash, you can also run ./myprog 2>/dev/null , which does the opposite: redirects all stderr stuff to nowhere, only showing the normal output (as if you had removed the fprintf(stderr,...) lines).

Questions?

It might be easier for you to think of recursive functions like this:

Code:

int f1 (int *a, int b) {
    int c;

    (*a)--;

    if (b>0) c = f2( &b,*a);
    else return *a;

    return b + c;
}

int f2 (int *a, int b) {
    int c;

    (*a)--;

    if (b>0) c = f3( &b,*a);
    else return *a;

    return b + c;
}

int f3 (int *a, int b) {
    int c;

    (*a)--;

    if (b>0) c = f4( &b,*a);
    else return *a;

    return b + c;
}

The problem can be thought of as entering another function that does the same thing. With the function written as above, can you now work out what the function will return?

You do your best to explain how you think it goes, and we will correct you.
That's the deal.