[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

recursive function

Posted on 2003-11-22
5
Medium Priority
?
547 Views
Last Modified: 2010-04-01
Hello, I am a student and I have a problem, I need to rewrite this code so that the function is recursive, but I have no idea where to start, the function is so basic that, to me, the function is fine, here is the code:

#include <iostream>

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

int linearSearch ( const int [], int, int );

int main ()
{
      const int arraySize = 100;
      int a [arraySize];
      int searchKey;

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

      cout << "Enter integer search key: ";
      cin >> searchKey;

      int element = linearSearch (a, searchKey, arraySize );

      if ( element != -1 )
            cout << "Found value in element " << element << endl;
      else
            cout << "Value not found" << endl;

      return 0;
            

}

int linearSearch ( const int array[], int key, int sizeOfArray )
{
      for ( int j = 0; j < sizeOfArray; j++ )
            if ( array[j] == key )
                  return j;

            return -1;
}


can any one give me any hints??
0
Comment
Question by:dabrat
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
5 Comments
 
LVL 4

Expert Comment

by:n_fortynine
ID: 9806366
EE policy does not allow experts to do homework for you, that is until a creditable amount of effort has been shown will advises be given. Well, as for hints... Think recursively! The first parameter can be viewed as the address to the first position in the array. After each unmatched comparison, you only have to consider the segment that comes AFTER this address only. What's the length of this segment? Where does it start?

Ring any bells?
0
 

Expert Comment

by:ks5d
ID: 9806399
Since this looks like a homework assignment, I can only give you general hints.

A recursive function is one that contains calls to itself.

Our textbook (Weiss, Data Structures & Problem Solving in C++) defines four "fundamental rules" for recursion:

1.  Base Cases:  Always have at least one case that can be solved without using recursion.

2. Make Progress:  Any recursive call must progress toward the base case.

3. "You gotta believe":  Always assume that the recursive call works.

4. Compound interest rule:  Never duplicate work by solving the same instance of a problem in separate recursive calls.

    For your particular problem, linearSearch will call itself until it finds an element of the array that matches the key, or the whole array has been searched.  These will be your base cases.

   Clearly, if linearSearch calls itself again & again with exactly the same values, it will never arrive at a solution or terminate.  Therefore, it is essential to write the recursive call so that the problem is getting smaller & smaller with each call.  A great canidate for this requirement is the parameter sizeOfArray.  Imagine a version of the function linearSearch that contains the following line:

return linearSearch(array, key, (sizeOfArray - 1);

I hope this helps,

             - Ken


0
 
LVL 4

Expert Comment

by:n_fortynine
ID: 9806421
>>3. "You gotta believe":  Always assume that the recursive call works.
And yet it betrayed me so many times :D j/k
0
 
LVL 5

Expert Comment

by:waelothman
ID: 9806952
First I have note that the recursive function is very slow than the iteration method but to do that as ks5d said you should divide your case into 2 cases
1 - simple case which the solution can calculated direct
2 - Other case which can simplefy to way to be the simble case

for example the factorial function n! = n*(n-1)*(n-2)*....*1
can divided into 2 case
 0! =  1
n! = n * (n-1)!

so the function will be
int fact (int n)
{
if (n==0) //the simple case
 return 1;
else  
  return n* fact(n-1); // the other case should simplify from n! -> (n-1)!
}

so your linear search should be the same try to find a simple case that you can determin the result and other case sholud be simple than the orginal case
try and let we know
0
 
LVL 1

Accepted Solution

by:
imstaff earned 80 total points
ID: 9854241
int linearSearch ( const int array[], int key, int sizeOfArray )
{
      if (key == array[sizeOfArray-1])
         return (sizeOfArray-1);
      else if ((sizeOfArray-1) >= 0)
                return linearSearch(array, key, (sizeOfArray - 1));
             else return -1;
}

hope it help
0

Featured Post

Important Lessons on Recovering from Petya

In their most recent webinar, Skyport Systems explores ways to isolate and protect critical databases to keep the core of your company safe from harm.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Written by John Humphreys C++ Threading and the POSIX Library This article will cover the basic information that you need to know in order to make use of the POSIX threading library available for C and C++ on UNIX and most Linux systems.   [s…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

656 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question