By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
454,128 Members | 1,059 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 454,128 IT Pros & Developers. It's quick & easy.

recurrsive function goes into infinte loop

nabh4u
P: 62
hi, i have a functionn sort_and_count where i will sort a vector and count the number of inversions. i will first divide the list into two n call the function recurrsively. problem is its going on,doesnt stop. please can you tell me why is this problem here? this implements merge sort also.
here's the sample code:

Expand|Select|Wrap|Line Numbers
  1. int sort_and_count(int Left,int Right)
  2. {
  3.      int Mid;
  4.      int count=0,countL=0,countR=0;
  5.      if(Left==Right)
  6.      {
  7.           return count=0;
  8.      }
  9.      else
  10.      {
  11.           Mid=(Left+Right+1)/2;
  12.           countL = sort_and_count(Left,Mid);
  13.           countR = sort_and_count(Mid+1,Right);
  14.           count = merge_count(Left,Mid,Right);
  15.           return count=count+countL+countR;
  16.      }    
  17. }
thank you in advance..
Mar 11 '07 #1
Share this Question
Share on Google+
3 Replies


P: 63
iLL
hi, i have a functionn sort_and_count where i will sort a vector and count the number of inversions. i will first divide the list into two n call the function recurrsively. problem is its going on,doesnt stop. please can you tell me why is this problem here? this implements merge sort also.
here's the sample code:

Expand|Select|Wrap|Line Numbers
  1. int sort_and_count(int Left,int Right)
  2. {
  3.      int Mid;
  4.      int count=0,countL=0,countR=0;
  5.      if(Left==Right)
  6.      {
  7.           return count=0;
  8.      }
  9.      else
  10.      {
  11.           Mid=(Left+Right+1)/2;
  12.           countL = sort_and_count(Left,Mid);
  13.           countR = sort_and_count(Mid+1,Right);
  14.           count = merge_count(Left,Mid,Right);
  15.           return count=count+countL+countR;
  16.      }    
  17. }
thank you in advance..

There is something wrong with your equation

1 = (0 + 1 + 1)/2 // Integral math

In the next line you state sort_and_count(Left,Mid); since Mid == Right, you’ll get into an infinite loop here.

Any time the difference between left and right is 1, then Mid == Right


therefore you’ll never get to the base case of left == right
Mar 11 '07 #2

P: 63
iLL
Maybe (note that I haven’t try it) if your base case is:

if((Right == Left) || (Right – Left = 1))
Mar 11 '07 #3

nabh4u
P: 62
There is something wrong with your equation

1 = (0 + 1 + 1)/2 // Integral math

In the next line you state sort_and_count(Left,Mid); since Mid == Right, you’ll get into an infinite loop here.

Any time the difference between left and right is 1, then Mid == Right


therefore you’ll never get to the base case of left == right
thanks for the insight...i have resolved the error...
the equations should be :
mid = (left+right)/2
Mar 13 '07 #4

Post your reply

Sign in to post your reply or Sign up for a free account.