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

This is a discussion on HELP! What does this code do? It has recursive function in it >:( within the C Programming forums, part of the General Programming Boards category; Can someone please help me with this code? I need the detailed explanation of what does it do...I'm a bit ...

  1. #1
    Registered User Jovana's Avatar
    Join Date
    Oct 2012
    Location
    Belgrade, Serbia
    Posts
    2

    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));
    }
    Last edited by Jovana; 10-07-2012 at 03:45 PM.

  2. #2
    qny
    qny is offline
    Registered User
    Join Date
    Sep 2012
    Posts
    355
    The code you posted does not compile.

    Also main returns an int, not void.
    and the indentation sucks.

  3. #3
    Registered User
    Join Date
    Oct 2012
    Posts
    1
    Your code doen't compile.
    Fix (a*)-- to (*a)--

  4. #4
    Registered User Jovana's Avatar
    Join Date
    Oct 2012
    Location
    Belgrade, Serbia
    Posts
    2
    Right, that's the spelling mistake...Sorry. I was typing it too fast.
    Anyway, I can't use compiler to get solution because:

    On the test, we are given the code, and we have to solve what it prints on our own, without any compiler, there on the blank paper.
    So, that's why I asked for help...if anyone can guide me step by step through this code.
    This recursive function gives me the most trouble...

    Please, help??

  5. #5
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  6. #6
    Left
    Join Date
    Oct 2011
    Posts
    816
    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?
    Last edited by Nominal Animal; 10-07-2012 at 05:48 PM.

  7. #7
    TEIAM - problem solved
    Join Date
    Apr 2012
    Location
    Melbourne Australia
    Posts
    1,303
    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?
    Last edited by Click_here; 10-07-2012 at 08:01 PM.
    Fact - Beethoven wrote his first symphony in C

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    You do your best to explain how you think it goes, and we will correct you.
    That's the deal.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Converting recursive function to tail recursive
    By ajacobs365 in forum C Programming
    Replies: 1
    Last Post: 10-30-2011, 08:15 AM
  2. Replies: 15
    Last Post: 05-11-2011, 05:06 PM
  3. Make Recursive function 'Tail-Recursive'
    By dp2452 in forum C Programming
    Replies: 7
    Last Post: 12-04-2009, 09:13 AM
  4. [code] Recursive Search Function
    By anonytmouse in forum Windows Programming
    Replies: 1
    Last Post: 12-17-2004, 10:21 PM
  5. Recursive Function in Pseudo Code
    By smitsky in forum Tech Board
    Replies: 3
    Last Post: 10-24-2004, 10:17 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21