LinuxQuestions.org
Share your knowledge at the LQ Wiki.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 02-02-2004, 03:10 PM   #1
TriggerJ
LQ Newbie
 
Registered: Sep 2003
Location: Texas
Posts: 14

Rep: Reputation: 0
Recursive Function


How would I change the binarySearch function into a recursive function in the following program?

Thanks,

Jessica

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <iomanip>

using std::setw;

int binarySearch (const int [], int, int, int, int);
void printHeader (int);
void printRow (const int [], int, int, int, int);

int main ()
{
const int arraySize=15;
int a [arraySize];
int key;

for (int i=0; i<arraySize; i++)
a[i]=2*i;

cout<< "Enter a number between 0 and 28: ";
cin>>key;

printHeader (arraySize);

int result =
binarySearch (a, key, 0, arraySize-1, arraySize);

if (result != -1)
cout<< '\n'<<key<< " found in array element "
<<result<<endl;
else
cout<<'\n'<<key<<" not found"<<endl;
return 0;
}

int binarySearch(const int b[], int searchKey, int low, int high, int size)
{
int middle;

while (low <= high)
{
middle= (low+high)/2;
printRow(b, low, middle, high, size);

if (searchKey == b[middle])
return middle;
else
if (searchKey<b[middle])
high=middle-1;
else
low=middle+1;
}
return -1;
}

void printHeader(int size)
{
cout<<"\nSubscripts:\n";

for (int j=0; j<size; j++)
cout <<setw (3)<<j<<' ';

cout<<'\n';

for (int k=1; k<=4*size; k++)
cout<<'-';

cout<< endl;
}

void printRow(const int b[], int low, int mid, int high, int size)
{
for (int m=0; m<size; m++)

if (m<low||m>high)
cout<<" ";
else
if (m==mid)
cout <<setw(3)<<b[m]<<'*';
else
cout<<setw(3)<<b[m]<<' ';
cout<<endl;
}
 
Old 02-02-2004, 03:48 PM   #2
Strike
Member
 
Registered: Jun 2001
Location: Houston, TX, USA
Distribution: Debian
Posts: 569

Rep: Reputation: 31
Smells like homework.
 
Old 02-02-2004, 05:50 PM   #3
crabboy
Moderator
 
Registered: Feb 2001
Location: Atlanta, GA
Distribution: Slackware
Posts: 1,823

Rep: Reputation: 120Reputation: 120
Code:
int binarySearch(const int b[], int searchKey, int low, int high, int size)
{
   int middle;

   middle = ( low + high ) / 2;
   printRow(b, low, middle, high, size);

   if ( searchKey > b[middle] )
      return binarySearch( b, searchKey, middle + 1 , high, size );
   else if ( searchKey < b[middle] )
      return  binarySearch( b, searchKey, low , middle - 1, size );
   else if ( searchKey == b[middle] )
      return middle;

   return -1;
}
 
Old 02-02-2004, 09:02 PM   #4
TriggerJ
LQ Newbie
 
Registered: Sep 2003
Location: Texas
Posts: 14

Original Poster
Rep: Reputation: 0
Thank you!!!
 
Old 02-02-2004, 09:58 PM   #5
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
Recursive functions are almost always a bad idea, though. Stack overflows and stuff can be nasty. If you have a non-recursive algorithm, it'd be better to stick with that.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
gcc: recursive function quirk Disruptor Linux - Software 4 09-23-2014 06:45 AM
Perl file handler in recursive function enemorales Programming 4 02-02-2009 04:20 PM
using return in recursive function hubabuba Programming 9 10-10-2005 10:59 AM
error recursive function in c shams Programming 3 07-28-2004 09:44 PM
A main can be changed by a function local without passing anything to the function? ananthbv Programming 10 05-04-2004 02:31 PM


All times are GMT -5. The time now is 05:44 PM.

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration