Page 1 of 1
recursion
Posted: Wed Jul 20, 2005 12:11 pm
by 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() ???
Re:recursion
Posted: Wed Jul 20, 2005 12:43 pm
by 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.
Re:recursion
Posted: Wed Jul 20, 2005 12:55 pm
by 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.
Re:recursion
Posted: Wed Jul 20, 2005 3:34 pm
by 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.
Re:recursion
Posted: Wed Jul 20, 2005 10:38 pm
by 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;
}
Re:recursion
Posted: Wed Jul 20, 2005 11:40 pm
by 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.
Re:recursion
Posted: Thu Jul 21, 2005 11:01 am
by 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.
Re:recursion
Posted: Thu Jul 21, 2005 11:29 am
by 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;
Re:recursion
Posted: Thu Jul 21, 2005 11:05 pm
by Neo
rich_m wrote:
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
Re:recursion
Posted: Fri Jul 22, 2005 1:37 am
by 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.
Re:recursion
Posted: Fri Jul 22, 2005 1:41 am
by AR
Is "true" meant to equal 0?
Re:recursion
Posted: Fri Jul 22, 2005 2:17 am
by Solar
No, Solar is meant to think while typing.
Of course true must be defined to 1.