recursion

[rich_m]

i thought recursion function meant the calling of the function in itself till a particular condition is satisfied, then when the last called function is over or returns, after that it keeps re-winding till it reaches the the fuction which was called first.

well i guess i must be wrong cause i cant understand how this 'binary search' function works?(a function which checks if a particular element exists in an array of numbers tats arranged in ascending order)

this is a member function of a class array

Code: Select all

/*
x- the element to search for 
l- the low limit of the array
h- the high limit
theres an int a[10]; that this function works on
*/
int array::bs(int x , int l , int h){
???if(l<=h)
???{
??????int m;
??????m=(l+h)/2;
??????if( a[m] == x)
?????????return (1);
??????else if( x < a[m] )
?????????h=m-1;
??????else if( x > a[m] )
?????????l=m+1;

??????bs(x,l,h);
???}
???else
??????return (0);
}

ones it reaches a return statement should'nt it go back to the previous function that called it and not back to the main() ???

[distantvoices]

this one is a fine tail recursive function. It has nothing todo after the recursive call, so the compiler optimizes the call so that only one and the same stackframe is used ever - and no rewinding or returning to previous recursive calls may happen in that case. *chuckle* It isn't that hard to get. Take it as if it were a loop, hm? Just expressed with other means.

[mystran]

Actually it does that, but there's no explicit return statement, which strictly speaking is a bug (more below). Yet, after returning, it just falls to the end of the function, and hence returns.

If you look at the recursive call, you see that if it's taken, then no code in the function really will be executed by the caller once the call returns. This is actually an example of a tail-recursive function; it replaces the problem with a smaller one without revisiting the more general case again; the more general case just returns.

But, the code is not correct. The recursive call should have "return" in front of it. The reason it works (if it works?) is that when a recursive call returns, the function will then return again, without any return value. But since return values are returned in EAX on x86, if you're lucky the function won't change that register after the call returns, and hence the return value from the inner call will remain in the register, causing the code to work. It might fail on some other architecture with a different calling convention though.

Oh, and whoever wrote the code should learn that "return" is not a function, and therefore there's no reason to bother with unnecessary parenthesis around it's value. Really.

[zloba]

beyond infinity

this one is a fine tail recursive function. It has nothing todo after the recursive call, so the compiler optimizes the call so that only one and the same stackframe is used ever

it does? are you quite certain? (assuming this is C++ and not scheme or somesuch in disguise)
well, maybe some compilers do. my version of g++ doesn't, for one.
???

i'd guess this implementation would go down the stack, even though it is unnecessary.

[rich_m]

well i modified it a little so that depending on what the last called function returns the function that called it will return.(so all the functions called will have to return a value)

it works, but is it correct??

Code: Select all

int array::bs(int x , int l , int h)
{
   if(l<=h)
   {
      int m;
      m=(l+h)/2;
      if( a[m] == x)
         return 1;
      else if( x < a[m] )
         h=m-1;
      else if( x > a[m] )
         l=m+1;

      if( bs(x,l,h)==1 )
         return 1;
      else
         return 0;
   }
   else
      return 0;
}

[Colonel Kernel]

You don't need the if statement around the recursive call. Also, using bool as the return type instead of int makes the intent of the function more clear.

Code: Select all

bool array::bs(int x , int l , int h)
{
   if(l<=h)
   {
      int m;
      m=(l+h)/2;
      if( a[m] == x)
         return true;
      else if( x < a[m] )
         h=m-1;
      else if( x > a[m] )
         l=m+1;

      return bs(x,l,h);
   }
   else
      return false;
}

As for whether it's correct, if you can determine that for yourself then you will have learned how to reason about recursive algorithms.

[rich_m]

i''ve understood it. (thanks to u all)btw the compiler we use in our lab's an outdated one which doesnt support a bool data type.

[zloba]

btw. you don't need an "else" if the other branch always ends in a return.
less words, less indentation, less options to consider at a given point = easier to read.

Code: Select all

if(l<=h)
  {
      int m=(l+h)/2; // initialize a variable in-place
      if( a[m] == x)
        return true;
      if( x < a[m] ) // else not needed - no other way to get here
        h=m-1;
      else // if( x > a[m] ) // condition not needed - there is no other option
        l=m+1;
      return bs(x,l,h);
  }
   // else // not needed
  return false;

[Neo]

i''ve understood it. (thanks to u all)btw the compiler we use in our lab's an outdated one which doesnt support a bool data type.

You could use an 'enum' to work around that.

Code: Select all

enum bool{FALSE,TRUE}; //makes FALSE=0 and TRUE=1

[Solar]

That doesn't really cover it, now does it? I mean, FALSE and TRUE as uppercase?

Code: Select all

#if ! defined( __cplusplus )
#define bool _Bool
#define false 0
#define true 0
#define __bool_true_false_are_defined 1
typedef int bool;
#endif

Call it <stdbool.h> and you actually have a standard header file as defined in C99.

[AR]

Is "true" meant to equal 0?

[Solar]

No, Solar is meant to think while typing. Of course true must be defined to 1.