Ileterative & recursive function

This is a discussion on Ileterative & recursive function within the C Programming forums, part of the General Programming Boards category; this code should calculate the greates common divisor of 2 integers entered by the user. Both the recursive & ilterative ...

  1. #1
    Registered User
    Join Date
    Jul 2004
    Posts
    46

    Question Ileterative & recursive function

    this code should calculate the greates common divisor of 2 integers entered by the user.
    Both the recursive & ilterative function should have the same result but they don't.
    I can't for the life of me figure out what im doing wrong.
    Any help would be much appreciated !

    Code:
    #include <stdio.h>
    int gcd(int a,int b);
    int gcdliterative(int a,int b);
    
    void main(){ 
      
      int a,b,c,d;
      printf("Enter two posetive integers,\n");
      printf("that you'd like to see the greatest common divisor off\n");
      if ((scanf("%d%d",&a,&b)) != 2){
    	  printf("Error!You needed to input 2 posetive integers, exiting...\n");
    	  exit(1);
      }
      c = gcd(a,b);
      printf("The greatest common divisor off:%d and %d is: %d\n",a,b,c);
      printf("Calculating again ,useing a literative loop this time\n");
      d = gcdliterative(a,b);
      printf("The greatest common divisor off:%d and %d is: %d\n",a,b,d);
    }
    
    int gcd(int a,int b){
      int r;
      if ((r = a % b) == 0)
    	  return b;
      else
         return gcd(b,r);
    }
    
    int gcdliterative(int a,int b){
       int r;
       while((r = a % b) == 1){
            a = b;
    		b = r;
       }
       return r;
    }

  2. #2
    Software Developer jverkoey's Avatar
    Join Date
    Feb 2003
    Location
    University of Waterloo
    Posts
    1,903
    Code:
     int gcdliterative(int a,int b){
        int r;
        while((r = a % b) == 1){
             a = b;
     		b = r;
        }
        return r;
     }
    k, you've got the right setup, just a few things out of order.

    First off, (r = a % b) == 1, notice in your recursive one how you test if the remainder is 0 then you return, but if it's anything OTHER then 0, you continue on again, right?

    Well, you need to apply that same logic here, instead of testing if the value is 1, test if it's not 0, in other words, just do:

    (r = a % b) != 0

    or you could even just do:

    (r = a % b)

    Both work the same way.

    Next problem is your return, you're returning r, but since the loop goes until r equals 0, the only thing r will ever be returned as is....0!
    So instead of returning r, you need to return b, just like you did in the recursive version of the problem.

    Here's the working version of the code:
    Code:
     int gcdliterative(int a,int b){
        int r;
        while((r = a % b)){
     		a = b;
     		b = r;
        }
        return b;
     }
    -Hope that helps!

  3. #3
    Registered User
    Join Date
    Jul 2004
    Posts
    46
    Oke cool , thanks very much for your help !

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 28
    Last Post: 07-16-2006, 11:35 PM
  2. Calling a Thread with a Function Pointer.
    By ScrollMaster in forum Windows Programming
    Replies: 6
    Last Post: 06-10-2006, 08:56 AM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 01:28 PM
  4. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 09:18 AM
  5. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM

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