Like Tree5Likes
  • 1 Post By quzah
  • 1 Post By grumpy
  • 1 Post By anthonyd
  • 1 Post By quzah
  • 1 Post By grumpy

gcd function

This is a discussion on gcd function within the C Programming forums, part of the General Programming Boards category; As an exercise I had to write a recursive function that computes the greater common denominator between two numbers. Before ...

  1. #1
    Charming Registered User
    Join Date
    May 2011
    Posts
    49

    gcd function

    As an exercise I had to write a recursive function that computes the greater common denominator between two numbers. Before the use of a few brain cells that made me write one good answer:
    Code:
    int gcd(int a, int b)
    {
    	if (b == 0)
    		return a;
    	else
    		return gcd(b, a % b);
    }
    I wrote the same function as follows:
    Code:
    int gcd(int a, int b)
    {
    	int temp;
    	
    	if (b != 0)
    	{
    		temp = b;
    		b = a % b;
    		a = temp;
    		gcd(a, b);
    	}
    	else
    		return a;
    }
    Although the program worked correctly I can't understand one thing.
    What happens to the functions that are expected to return a value (int) but they won't return any?
    They do not seem to wrap up after gcd(a, b=0) returns the correct result to the program.

    Thank you for your time to read my post !!!

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    They both always return something.

    edit - Ah, I see you aren't returning where you should:
    Code:
    	if (b != 0)
    	{
    		temp = b;
    		b = a % b;
    		a = temp;
    		return gcd(a, b);
    	}

    Quzah.
    Last edited by quzah; 06-07-2011 at 05:40 PM.
    ardavirus likes this.
    Hope is the first step on the road to disappointment.

  3. #3
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    Yes but let's say in the way of the return value some functions won't return anything. For example gcd(24,16) will compute the values for a and b and then will call gcd(16,8) but will not arrive at the return point.
    My question is, if the machine meet up with a function (during a recursive computation) that is expected to return something (an int in that case) but doesn't return anything, is ok with that?

  4. #4
    Registered User
    Join Date
    Jun 2005
    Posts
    6,203
    Quote Originally Posted by ardavirus View Post
    What happens to the functions that are expected to return a value (int) but they won't return any?
    If a function that returns any type other than void returns in any manner other than by an explicit return statement, the behaviour is undefined.

    That means anything is allowed to happen. The compiler is not required to diagnose an error. The program may crash when run. In practice, a common result is returning some junk value to the caller.
    ardavirus likes this.
    Right 98% of the time, and don't care about the other 3%.

  5. #5
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    That means that the second function is wrong cause is subject to undefined behavior ?

    Is it safe to generalize and say that recursive functions that won't wrap up is a bad practice ?
    Last edited by ardavirus; 06-07-2011 at 08:41 AM.

  6. #6
    Registered User
    Join Date
    Jun 2011
    Posts
    4
    As Wernher von Braun said: "One test result is worth one thousand expert opinions."

    A non void function always returns something, even if you don't have a return statement, but what it will return in that case is anybody's guess.
    The fact that your function is recursive does not make a difference in this case. The recursion will eventually stop and the execution will eventually resume back at the caller of the recursive function, but the values propagated will probably be wrong.

    Try the following code (to make von Braun happy):
    Code:
    #include <stdio.h>
    
    int f(int x){
        if( x == -354 )
            return 13;
    }
    
    int main(int argc, char **argv){
        int ret_val;
    
        ret_val = f(argc);
        printf("f() returned: %d\n",ret_val);
    
        return 0;
    }
    BTW, if you use "-Wall" most compilers should warn you about the missing "return".
    gcc 4.2 for example, says: "warning: control reaches end of non-void function" for the program above.
    ardavirus likes this.

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by ardavirus View Post
    Yes but let's say in the way of the return value some functions won't return anything. For example gcd(24,16) will compute the values for a and b and then will call gcd(16,8) but will not arrive at the return point.
    Then your compiler should be complaining at you, telling you that you wrote your function wrong.


    Quzah.
    ardavirus likes this.
    Hope is the first step on the road to disappointment.

  8. #8
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    @anthonyd
    Thank you very much for your analytical answer my friend. After this I can say that I own the question :-)

  9. #9
    Registered User
    Join Date
    Jun 2005
    Posts
    6,203
    Quote Originally Posted by ardavirus View Post
    That means that the second function is wrong cause is subject to undefined behavior ?
    Yes.
    Quote Originally Posted by ardavirus View Post
    Is it safe to generalize and say that recursive functions that won't wrap up is a bad practice ?
    I would say so, yes. Infinitely recursive functions will eventually consume more resources than the computer has available.
    ardavirus likes this.
    Right 98% of the time, and don't care about the other 3%.

  10. #10
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    @grumpy
    Thank you very much for the direct answers, you were very helpful !!!

    @quzah
    Thank you very much as well, the correction you put in my "erroneous" function cleared the fog much more.

    This forum provides the best help a self-teaching novice like me can get, I am infinitely in debt.

  11. #11
    Charming Registered User
    Join Date
    May 2011
    Posts
    49
    @grumpy
    Thank you very much for the direct answers, you were very helpful !!!

    @quzah
    Thank you very much as well, the correction you put in my "erroneous" function cleared the fog much more.

    This forum provides the best help a self-teaching novice like me can get, I am infinitely in debt.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 15
    Last Post: 06-09-2009, 02:19 AM
  2. Replies: 2
    Last Post: 02-26-2009, 10:48 PM
  3. Print function: sending a function.. through a function?
    By scarlet00014 in forum C Programming
    Replies: 3
    Last Post: 11-05-2008, 04:03 PM
  4. Replies: 14
    Last Post: 03-02-2008, 12:27 PM
  5. Replies: 9
    Last Post: 01-02-2007, 03:22 PM

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