4 Replies - 272 Views - Last Post: 09 April 2019 - 11:50 AM Rate Topic: -----

#1 hts   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 03-April 19

Recursive Linear Search Java

Posted 09 April 2019 - 09:34 AM

For this assignment, I'm supposed to edit this code (below) to use the recursive method recursiveLinearSearch to perform a linear search of the array. The method should receive the search key and the starting index as arguments. If the search key is found, return its index in the array; otherwise return -1. Each call to the recursive method should check one index in the array.

The problem is I have no idea how to do it. I've been going through our textbook and googling everything that I can about the recursive method and nothing has helped. Our textbook doesn't even mention the method. So that's frustrating and my professor refuses to help. And I just need help. Any and all advice will be greatly appreciated...like how should I start it? What website should I read?

package week6;

import java.security.SecureRandom;
import java.util.Arrays;
import java.util.Scanner;

public class Week6 //Linear search test fig. 19.2
{
    // perform linear search
    public static int linearSearch(int data[], int searchKey)
    {
        for (int index = 0; index < data.length; index++)
            if (data[index] == searchKey)
                return index; //return index of integer
        
        return -1; //integer was not found
    }
    
    public static void main(String[] args) 
    {
        Scanner input = new Scanner(System.in);
        SecureRandom generator = new SecureRandom();
        
        int[] data = new int[10]; //create array
        
        for (int i = 0; i <data.length; i++) // populate array
            data[i] = 10 + generator.nextInt(90);
        
        System.out.printf("%s%n%n", Arrays.toString(data)); // display array
        
        //get input from user
        System.out.print("Please enter an integer value (-1 to quit): ");
        int searchInt = input.nextInt();
        
        // repeatedly input an integer; -1 terminates the program
        while (searchInt != -1)
        {
            int position = linearSearch(data, searchInt); //perform search
            
            if (position == -1) // not found
                System.out.printf("%d was not found%n%n", searchInt);
            else //found
                System.out.printf("%d was found in position %d%n%n", searchInt, position);
            
            // get input from user
            System.out.print("Please enter an integer value (-1 to quit): ");
            searchInt = input.nextInt();
        }
        
    } // end main
    
} //end class


Is This A Good Question/Topic? 0
  • +

Replies To: Recursive Linear Search Java

#2 modi123_1   User is online

  • Suitor #2
  • member icon



Reputation: 14995
  • View blog
  • Posts: 59,871
  • Joined: 12-June 08

Re: Recursive Linear Search Java

Posted 09 April 2019 - 09:39 AM

Is the issue you do not understand recursion, or do not understand how recursion would apply to this specific problem?
Was This Post Helpful? 0
  • +
  • -

#3 Martyr2   User is offline

  • Programming Theoretician
  • member icon

Reputation: 5404
  • View blog
  • Posts: 14,310
  • Joined: 18-April 07

Re: Recursive Linear Search Java

Posted 09 April 2019 - 09:50 AM

Recursion is a fancy way of saying "A function that calls itself until some condition is met". Usually with a subset of data that was originally input. So for instance if I have a method called recursiveLinearSearch that takes a key and an array of values, inside that function it is going to call itself (that is, it is going to make a call to recursiveLinearSearch again) but with perhaps only half the original array. In your case, the condition that needs to be met is that the value is found or all input values have been exhausted.

private int recursiveLinearSearch(int data[], int key,  int startingIndex) {
    // if the startingIndex in data is key, return startingIndex OR startingIndex = highest index in data (usually length of array - 1)  <---- This is your condition that will stop the recursion
    // Otherwise call recursiveLinearSearch again, giving it data, key and the next starting index. In a linear search do you know what that values is? 
  
}



So that is where I would start. Plenty of hints in there to get you started on the right path and how to think about recursion. To make recursion easy to code, always start by thinking what is my condition to stop the recursion (aka "base case"). Without a base case, you will continuously keep calling itself without stopping.
Was This Post Helpful? 1
  • +
  • -

#4 hts   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 03-April 19

Re: Recursive Linear Search Java

Posted 09 April 2019 - 11:01 AM

Thank you so much!
Was This Post Helpful? 0
  • +
  • -

#5 hts   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 03-April 19

Re: Recursive Linear Search Java

Posted 09 April 2019 - 11:50 AM

View PostMartyr2, on 09 April 2019 - 09:50 AM, said:

Recursion is a fancy way of saying "A function that calls itself until some condition is met". Usually with a subset of data that was originally input. So for instance if I have a method called recursiveLinearSearch that takes a key and an array of values, inside that function it is going to call itself (that is, it is going to make a call to recursiveLinearSearch again) but with perhaps only half the original array. In your case, the condition that needs to be met is that the value is found or all input values have been exhausted.

private int recursiveLinearSearch(int data[], int key,  int startingIndex) {
    // if the startingIndex in data is key, return startingIndex OR startingIndex = highest index in data (usually length of array - 1)  <---- This is your condition that will stop the recursion
    // Otherwise call recursiveLinearSearch again, giving it data, key and the next starting index. In a linear search do you know what that values is? 
  
}



So that is where I would start. Plenty of hints in there to get you started on the right path and how to think about recursion. To make recursion easy to code, always start by thinking what is my condition to stop the recursion (aka "base case"). Without a base case, you will continuously keep calling itself without stopping.


For this assignment the values are randomly generated (if that's what you're asking!)

View Postmodi123_1, on 09 April 2019 - 09:39 AM, said:

Is the issue you do not understand recursion, or do not understand how recursion would apply to this specific problem?


My issue is both of those things.. I'm starting to understand recursion a little bit more the more I read about it online, but I'm not sure how to apply it to this problem..
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1