Linear search using recursive function
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Linear search using recursive function

  1. #1
    Join Date
    Apr 2006
    Posts
    2

    Linear search using recursive function

    Hello,

    I'm new here and am seeking some help with an assignment. I understand that a recursive function calls itself. However, I've been working on this assignment for some time and can't get it to work. Can someone help by stating what part of my code is wrong and explain why? I'm confused because I don't understand how a recursive function would handle an array. I've searched and only found the Fibonacci Series.

    The assignement is to use a recursive function called linearSearch to perform linear search of the array. The function should receive an interger array and the size of the array as arguments. If the search key is found, return the array subscript; otherwise, return -1.

    Thank you very much for any help.

    Code:
    #include <iostream>
    #include <conio.h>
    using namespace std;
    
    int linearSearch( int [], int );
    
    int main()
    {
       const int arraySize = 100;
       int a[arraySize];
       int element;
    
       for( int i = 0; i < arraySize; i++)
       {
          a[i] = 2 * i;
       }
    
       element = linearSearch( a, arraySize );
    
       if( element != -1 )
          cout << "Found value in element " << element << endl;
    
       else
          cout << "Value not found." << endl;
    
       getch();
       return 0;
    }
    
    int linearSearch( int array[], int counter )
    {
       if( linearSearch( array, counter - 1 ) != 10 )
          return counter;
       else
        return -1;
       
    }

  2. #2
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: Linear search using recursive function

    Code:
    #include <iostream>
    #include <conio.h>
    using namespace std;
    
    /*
    	Linear Search
    Description:
    	Searches array recursively for value 10.*/
    int linearSearch(int array[],int counter) {
    	--counter;
    	if (counter < 0)
    		return -1; // value not found
    	if (array[counter] == 10)
    		return (counter+1); // found value at returned position (index starting with 1)
    	else
    		return linearSearch(array,counter); // continue search
    }
    /*
    	Conventional entrypoint of the application
    Description:
    	Allocates an array of 100 elements with values as even numbers starting with 0 and then calls the linearSearch function.*/
    int main() {
    	const int arraySize = 100;
    	int a[arraySize];
    	register int i = arraySize;
    	while (i) { --i;
    		a[i] = 2 * i;
    	}
    	int element = linearSearch(a,arraySize);
    	if (element < 0) { // element not found
    		cout << "Value not found." << endl;
    	}
    	else { // element found
    		cout << "Found value in element # " << element << endl;
    	}
    	getch();
    	return 0;
    }
    Best regards,
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  3. #3
    Join Date
    Apr 2006
    Posts
    2

    Re: Linear search using recursive function

    Thank you for your help. This will help me a lot with the other recursion assignments. Thanks again.

  4. #4
    Join Date
    Sep 2005
    Location
    United States
    Posts
    799

    Smile Re: Linear search using recursive function

    I would assume that your professor is only giving this assignment to ease you into understanding how recursion works.

    A lot of overhead is created here because function calls have to be allocated on the stack, and for something so trivial as a linear search a lot of resources will be wasted by using recursion.

    An alternative, and more efficient way to coding a linear search.
    ( not that doing linear searching is really efficient anyways )

    Code:
    #include <iostream>
    using namespace std;
    
    int main()
    {
       const int arraySize = 100;
       int a[arraySize];
       int element;
    
       cout << "Enter element to search for: ";
       cin >> element;
       cout << endl;
    
       for ( int i=0; i < arraySize; i++ ){
          if ( element == a[ i ] ){
              cout << "Element found at location " << i << endl;
              break;
          }
       }
    
       return 0;
    }
    Here, you don't even need to use a function because the code is so small. Not trying be mean or anything, as I am sure your professor made you do it that way, and I am plenty used to professors giving me retarded examples to illustrate certain concepts in C++. Just trying to show ya another way of doing it for future reference

  5. #5
    Join Date
    Jan 2004
    Location
    Düsseldorf, Germany
    Posts
    2,401

    Re: Linear search using recursive function

    I hope, you are aware that you are searching backwards. The result will be (maybe) unexpected if your array contains two 10s.

  6. #6
    Join Date
    Oct 2013
    Posts
    2

    Re: Linear search using recursive function

    Quote Originally Posted by treuss View Post
    I hope, you are aware that you are searching backwards. The result will be (maybe) unexpected if your array contains two 10s.
    Another example that can be helpful

    http://fahad-cprogramming.blogspot.com/2014/02/linear-search-program-in-c-using.html

  7. #7
    Join Date
    Feb 2014
    Location
    India
    Posts
    5

    Re: Linear search using recursive function

    Also I suggest that you do a bit more research on recursion. The more you study about it, the more you understand how easy it is ( equivalent to writing a simple formula ). The reason I'm saying this because it is a vastly used technique and considered good software engineering if you plan to become one. Moreover it is more understandable by another user who is to edit your code and given an edge over looping ( as long as your stack doesn't blow up ). Indeed your professor chose a poor example to illustrate the concept but what can he do. He can't make you write 1000 lines of code and just say to his students that the only point was to show that recursion is a good technique. It may very well be the last thing he says...

  8. #8
    Join Date
    Jul 2013
    Posts
    220

    Re: Linear search using recursive function

    Quote Originally Posted by dcjr84 View Post
    A lot of overhead is created here because function calls have to be allocated on the stack, and for something so trivial as a linear search a lot of resources will be wasted by using recursion.
    Are you sure?

    Tail recursion is well studied and a staple of functional programming. Most C++ compilers will be able to replace tail recursion with an iterative equivalent so there will be no runtime penalty.

  9. #9
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,782

    Re: Linear search using recursive function

    Quote Originally Posted by razzle View Post
    Are you sure?

    Tail recursion is well studied and a staple of functional programming. Most C++ compilers will be able to replace tail recursion with an iterative equivalent so there will be no runtime penalty.

    YEs, I'm sure.

    it may be well studied, but it's still not a good idea to rely on compiler features to obtain a certain effect. Expecting a compiler to turn a recursive call into an iterative process is quite a stretch to rely on.

    This one in particular I would consider "a bad example of recursion", yes, you can enforce any iterative process into a recursive one, but that doesn't mean it's logical or straightforward to do so. A linear search is at heart an iterative process, so it makes little sense to try and turn it into a recursive solution. I.m.o. it will cause more confusion to the students than it actually solves because of the inate "weird way of thinking". In that light, I would say this is a bad example of using recursion.



    Fibonacci numbers are a good example of where it "makes sense", but where at the same time there is a strong motivation against using recursion because of excessive runtime for the higher numbers (mainly caused by the double recursive call). So it's a good example of where recursion might be intuitive, yet inappropriate because recursion comes at a cost.

    Other good examples would be directory searches, tree/menu traversal, quicksort, radix sort, expression parsing (ok, quite advanced this one), several "AI" techniques such as pathfinding, fill algorithms, ...

  10. #10
    Join Date
    Apr 2000
    Location
    Belgium (Europe)
    Posts
    3,782

    Re: Linear search using recursive function

    Quote Originally Posted by parikshit6321 View Post
    Indeed your professor chose a poor example to illustrate the concept but what can he do. He can't make you write 1000 lines of code and just say to his students that the only point was to show that recursion is a good technique.
    Seeing this quite a lot tbh. Poor examples because of lazyness of the person writing the exercices.

    If recursion isn't intuitive, then i.m.o. it's a bad idea to try and use it as an example.

    There are plenty of simple exercies where you can intuitively explain why recursion would be a good fit and not require 1000 lines of code to write to see it happen.

    replacing a for-loop by a recursive call is imo a horribad example.

  11. #11
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,269

    Re: Linear search using recursive function

    Personally, I like the towers of Hanoi as an example. The whole program is only about a dozen lines.
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  12. #12
    Join Date
    Oct 2008
    Posts
    1,088

    Re: Linear search using recursive function

    Quote Originally Posted by OReubens View Post
    If recursion isn't intuitive, then i.m.o. it's a bad idea to try and use it as an example.
    ... unless it is a functional programming course where immutability is a requirement and loop-like imperative solutions are not possible even in principle. That said, I too wonder what's the point of introducing functional programming concepts in a basic C or C++ course ...

    Moreover, I'm not so sure that such optimization actually always takes place, at least so reliably to advocate its use by non experts. For example, how does tail recursion works with varying calling conventions ? how does it interact with the more and more common use of RAII making so easy to write "apparent" tail recursive functions ? what about exceptions ? ...

  13. #13
    Join Date
    Jul 2013
    Posts
    220

    Re: Linear search using recursive function

    Quote Originally Posted by OReubens View Post
    YEs, I'm sure.
    No you're opinionated and/or have never used a functional language.

    Your "advice" as to when recursion is appropriate is very arbitrary to say the least. For example visiting the first 10 nodes of a list and generating the first 10 Fibonacci numbers both represent linear sequences that can be formulated both iteratively and recursively. Still the former would be a bad example of recursion while the latter would make sense. Why really?

    My reply to dcjr84 (although he isn't likely to read it ten years after ) was regarding tail recursion specifically. It's a special case and both GCC and VC++ replace it with iteration (in release mode optimized for speed). Yes you can rely on that.

    So if a sequence has a natural tail recursive definition I would consider using it. And if you're into template metaprogramming you don't have much of a choise because recursion is your only option.
    Last edited by razzle; February 19th, 2014 at 12:15 AM.

  14. #14
    Join Date
    Jul 2013
    Posts
    220

    Re: Linear search using recursive function

    Quote Originally Posted by superbonzo View Post
    That said, I too wonder what's the point of introducing functional programming concepts in a basic C or C++ course ...
    I was surprised that C++ was used as model language in what seems like a basic programming course. But then I realized this thread is almost 10 years old and at that time the marginalization of C++ in education wasn't yet as pronounced as today.

    Most introductory C++ courses held at colleges and universities are for advanced students and since C++ is a multiparadigmic language I see no reason why predominantly functional concepts like say recursion and lambda expressions should be left out.
    Last edited by razzle; February 19th, 2014 at 04:31 AM.

  15. #15
    Join Date
    Jul 2013
    Posts
    220

    Re: Linear search using recursive function

    Quote Originally Posted by OReubens View Post
    replacing a for-loop by a recursive call is imo a horribad example.
    You're absolutely right.

    As we all know C++ is especially well suited for us old-timers with an ancient education who want to hang on to C style coding the last few years before retirement. A good example of the versatility of C++ is the while-loop, an adventurous alternative to the more secure for-loop. But of course it should only be used when absolutely necessary and with uttermost care. Or as we so succinctly express it at my shop: Go for for, use while in a while!

    Functional programming. Object orientation. Template metaprogramming. Recursion. Lambda expressions. Smart pointers. Concurrency. Devirualization. Tail call removal. What bull is this? Have people gone raving mad!!!
    Last edited by razzle; February 20th, 2014 at 02:57 AM.

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center