CODEWITHSUNDEEP
crecursion
sonlas10
sonlas10

Reputation: 175

Fail in recursion with odd numbers

I have just write this funtion to print a list with the numbers between a and b.

void list(int a, int b){

  if(a == b){
    printf("%d", a);
  }else{
    if(a < b){
      printf("%d ", a);
      printf("%d ", b);
      list(a + 1, b - 1);
    }
    if(b < a){
      printf("%d ", a);
      printf("%d ", b);
      list(a - 1, b + 1);
    }
  }

}

When I call from the main the funtion, it works just when the number of numbers is odd. For example:

int main(){

  list(2, 8);

  return 0;
}

It works correctly and it prints: 2 8 3 7 4 6 5. But in this case:

int main(){

  list(2, 7);

  return 0;
}

It prints 2 7 3 6 4 5 5 4 4 5 5 4 4 5 5 4 4 5 5 4 4... forever.

What is wrong in the function??

Upvotes: 0

Views: 54

Answers (4)

sudheer naidu
sudheer naidu

Reputation: 162

In each turn when a is not equal to b, you are incrementing one(of a or b) and reducing the other. so the difference between the numbers now decrease by 2 (or increase by 2). Simple observation says that for termination of the re-calling the function, the numbers (a,b) have to be equal. so, for the difference to be 0 (a=b, which will not call the function again), the difference between a and b in the starting should be a multiple of 2. so only both even or both odd are acceptable. In other situations, the function will be called again and again and a particular sequence will repeat(in your case 4 5 5 4)

Upvotes: 0

Itati
Itati

Reputation: 193

(2,7)

2 7 3 6 4 5

When a = 4, b = 5, the next is a = 5, b = 4, so you got the loop.

try this:

void list(int a, int b){ 
  if ( ( b-a ) % 2  == 0 ){ // even
    if(a == b){
    printf("%d", a);
  }else{
  if(a < b){
    printf("%d ", a);
    printf("%d ", b);
    list(a + 1, b - 1);
  }// if
    else if(b < a){
      printf("%d ", a);
      printf("%d ", b);
      list(a - 1, b + 1);
    }
  }
}
else { // odd
  if(a < b){
    printf("%d ", a);
    printf("%d ", b);
    list(a + 1, b - 1);
  }  // if
 }
}

Upvotes: 0

Amir Fakhim Babaei
Amir Fakhim Babaei

Reputation: 1661

It's because it never ends. When the difference between a and b is odd, they never reach the == condition and it continues forever. To solve this, you can check if a and b are going to pass each other, kike this:

void list(int a, int b)
{
    if(a == b)
        printf("%d", a);

    else if(a < b)
    {
        printf("%d ", a);
        printf("%d ", b);
        
        if (a + 1 != b)
            list(a + 1, b - 1);
    }

    else if(b < a)
    {
        printf("%d ", a);
        printf("%d ", b);
        
        if (b + 1 != a)
            list(a - 1, b + 1);
    }
}

Upvotes: 1

Rom&#225;n
Rom&#225;n

Reputation: 146

As everytime you are making an iteration, you are substracting/adding 1 to both a and b. This means that when it is an odd number and a pair number a and b Will never be the same. I recommend you that when you start learning basic algorithms (specially for recursivion) you try some iterations on paper.

EDIT: A recommendation would be to simply add an exit clause (another else if), where you exit recursión if a becomes bigger than b (or viceversa, depending on which number was higher, you could save it in a boolean).

Upvotes: 0

Related Questions