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;
}
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,
Re: Linear search using recursive function
Thank you for your help. This will help me a lot with the other recursion assignments. Thanks again.
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 :)
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.
Re: Linear search using recursive function
Quote:
Originally Posted by
treuss
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
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 :D). 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...:D
Re: Linear search using recursive function
Quote:
Originally Posted by
dcjr84
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.
Re: Linear search using recursive function
Quote:
Originally Posted by
razzle
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, ...
Re: Linear search using recursive function
Quote:
Originally Posted by
parikshit6321
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.
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. :thumb:
Re: Linear search using recursive function
Quote:
Originally Posted by
OReubens
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 ? ...
Re: Linear search using recursive function
Quote:
Originally Posted by
OReubens
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.
Re: Linear search using recursive function
Quote:
Originally Posted by
superbonzo
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.
Re: Linear search using recursive function
Quote:
Originally Posted by
OReubens
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!!!
Re: Linear search using recursive function
Even in 2006 I would have replaced a for loop, while loop or the use of recursion to implement the linear search here with a call to std::find... except that this was an exercise specifically to practice recursion.
I don't see anything wrong (certainly not "retarded") with giving an introductory level assignment to implement linear search using recursion: it is a baby step to help students understand recursion through practice. Factorial is my own personal favourite introductory example, yet its typical recursive implementation has the same tail recursive structure that can be so easily replaced by iteration. My objection to the assignment is that -- if GrassPuppet stated it accurately -- it implies that the search key is to be hardcoded, and having students practice that doesn't seem good to me, but that's just a minor detail.
If we talking about say, what approach to choose should we be standard library authors implementing std::find (or more likely std::find_if), on the other hand, then I would pick iteration rather than recursion: it is easy to understand and straightforward to implement either way, so I might as well go for an implementation that does not rely on tail call elimination optimisation to be efficient.
Re: Linear search using recursive function
Quote:
Originally Posted by
superbonzo
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 ? ...
Some months ago, I implemented a basic recursive flood fill. It worked just fine with the small bitmaps (90x90 IIRC) it was used for in that appliction. Then I added a simple, harmless (at least seemingly) function call at the end of the function, right after the last of the four conditional recursive calls, and instantly the flood fill blew out the stack, even with smaller/less complex bitmaps I used for testing. The stack overhead of the additional function call was neclectible, and in particular since the call was made after the recursive calls, I wouldn't have expected it to have any effective impact on the stack at all (and in fact it didn't, as it turned out).
I spent quite some time pulling out my hair until I noticed that the compiler had applied tail recursion optimization to the last one of the four recursive calls, and, of course, the additional function call disabled the compiler to do that optimization, causing a massive increase in stack impact as an obscure side effect. Eventually I changed the true recursive implemtation into one utilizing a stack container, and that did the trick. Admittedly, the code looked far less intuitive after that change, though.
Though, here, I actually hit the problen due to my failure to consider that the compiler might apply tail recursion optimization to this four-fold recursion, instead of me relying on the optimization to take place, which somewhat is the exact opposite, I think it's related here.
Re: Linear search using recursive function
Quote:
Originally Posted by
razzle
No you're opinionated and/or have never used a functional language.
Now who's opinionated and even making unfounded assumptions.
Do I have an opinion, yes, obviously or I wouldn't be posting here in the first place.
Have I used functional languages before: yes, I'm not sure what led you to believe/assume I haven't.
And even in functional languages I'm STILL sure. Even there resursion comes at a higher cost than iteration (assuming iteration is even possible).
Quote:
Your "advice" as to when recursion is appropriate is very arbitrary
maybe... and maybe I'm right in asserting it that way.
if a recursive soluition to a problem doesn't "feel" natural to students (or a programmer in general) then maybe that is the very reason why it is inappropriate.
If the instinctive / intuitive thought is to solve it by iteration, then iteration is probably the better solution anyway because it's likely to be faster and more forgiving towards stack usage.
Quote:
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?
Because the very definition of Fibonacci numbers is recursive (the sum of the previous two Fibonacci numbers). If the definition is recursive, then surely the solution must be too...
Whereas searching nodes in a list... I guess it depends on how you formulated the problem you might get students to think towards a recursive solution.
Quote:
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.
Tail recursion is typically easy enough to spot and turn into an iterative call instead. and be sure of what you'll get without risking to blow up the stack.
Even with VC++ and optimize speed, it isn't a guarantee. And even if it is turned into an iteration it still isn't a guarantee it'll be as optimal because it'll often keep evaluating the edge/termination conditions.
And then... there are lots of compilers that don't optimize tail recursion into iteration. Or you have code that is incredibly slow in debug builds (or overflows the stack). In a student setting, you can't assume your students will only ever be working with VS or GCC, if you are touching recursion it's important to tell them about the problems associated with recursion.
If performance or potential stack overflow is important, you'd better do the conversion to iteration by hand. if neither performance or potential stack overflow is important... then it doesn't even matter if the compiler does it for you or not.
Quote:
And if you're into template metaprogramming you don't have much of a choise because recursion is your only option.
and if you have no other option, then again it doesn't matter, you have no alternative but to use what there is, that doesn't mean the template-metaprogramming-solution-with-recursion for a particular problem is necessarily the intuitive solution, and we're talking "entry level" students here, template metaprogramming is pretty advanced stuff.
I've seen quite a few elaborate template metaprogramming contortions where they end up slowing down compilation EVERY TIME because the compiler has to chew through the code, when the better solution would have been to precalculate the values and use some smart macro's to select between the values instead.
Macro's aren't ideal, but I don't want my compilations to take minutes because someone had the clever idea to calculate PI with a beast of a template metaprogramming technique (fictitional case). ANd no I'm not saying there is no place for template metaprogramming because obviously there is, but you can take it to undesired extremes.
Re: Linear search using recursive function
Quote:
Originally Posted by
OReubens
And even in functional languages I'm STILL sure. Even there resursion comes at a higher cost than iteration (assuming iteration is even possible).
No it doesn't. From the Wikipedia entry to functional programming:
"Iteration (looping) in functional languages is usually accomplished via recursion. Recursive functions invoke themselves, allowing an operation to be performed over and over until the base case is reached. Though some recursion requires maintaining a stack, tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages."
So in functional languages you loop by recursion and it's as efficient as iteration. Since you obviously don't know this I assumed you've never used a functional language.
Quote:
if a recursive soluition to a problem doesn't "feel" natural to students (or a programmer in general) then maybe that is the very reason why it is inappropriate.
If the instinctive / intuitive thought is to solve it by iteration, then iteration is probably the better solution anyway because it's likely to be faster and more forgiving towards stack usage.
This instinctive, intuitive and natural "feel" for iteration vs. recursion, where does it come from do you think? Lots of good things in programming is counter-intuitive and what you do instinctively is sometimes downright bad. In my view one of the most important aspects of education is to counteract preconceived "knowledge". I'm still thankful to my alma mater who had the courage to use Lisp as model language in the freshman CS course.
And what about yourself. Do you have the "feel" really? Have a look at the next quote.
Quote:
Because the very definition of Fibonacci numbers is recursive (the sum of the previous two Fibonacci numbers). If the definition is recursive, then surely the solution must be too...
The natural numbers 1,2,3,... are also recursively defined (the previous number plus 1).
Now what do you say? The definition is recursive so this sequence surely must be recursively generated just like your "feel" told you in the Fibonacci case. No? Why not?
Quote:
If performance or potential stack overflow is important, you'd better do the conversion to iteration by hand.
Your underlying assumption is that iteration is always faster than recursion and the only way to improve performance is to replace recursion with iteration.
A good counter-example is algorithms such as parallel_for where so called recursive parallelism is used to utilize multiple processor cores. Here recursion is used to improve on iteration.
So when you're using libraries such as Microsoft PPL and Intel TBB and apply what looks like typical imperative style iteration chances are there's a whole lot of recursion going on behind the scene.
---
I could go on and on but I quit here. Your argumentation doesn't hold up and you're stuck in old thinking.
