The stack search is recursive, but leave the stack intact

Question

I am trying to write a recursive function that searches for a stack but leaves the stack in its original state. I can pus h and pop the stack, but not use the auxiliary stack or any other data structure.

And yes, this is homework, so I do not expect a full encoded answer :). A little bit about how to approach the stack so that after the recursive search is complete the stack is intact.

A recursive function that looks for the stack for a specific element (but destroys the stack) is shown below:

template <class Type> Type getNth(stack(Type) & s, int n) { if(s.empty()) return -1; if(s.top() == n) return s.top(); if(s.top() != n && s.empty()) return -1; else s.pop(); return getNth(s, n); } 

It still works. Any help is much appreciated

Answer 1

before returning, you should save the value of pop() ed and the result of the recursive call and push() value of pop() ed before returning.

your other should look something like this: [besides him, he looks good]

 else temp = s.pop(); retVal = getNth(s, n); s.push(temp); return retVal; 

(*) forgive me for declaring temp and retVal , you can understand the general idea from this.

---

EDIT:
I decided to add a simple example of what happens, suppose your stack

 |1| |2| |3| |4| --- 

and you call getNth (s, 3): this is what will happen to the stack
after 1st pop () and getNth (): [the stop condition has not been reached, so keep moving]

 |2| |3| |4| --- 

2nd pop (), getNth (): [again, keep going]

 |3| |4| --- 

now when you check s.top () == n, you understand that it is! therefore you return n. When returning from recursion, s.push(temp) and temp==2 called, so we get:

 |2| |3| |4| --- 

and return retVal again, go back from recursion, we use s.push() again, and we get:

 |1| |2| |3| |4| --- 

source stack! and return the same returnVal that was returned by recursion!

NOTE. . This is not your question, but the name of the function means that you do not want to return the value you were looking for, but the nth element on the stack if your stack is:

 |5| |8| |8| |8| |2| |4| --- 

getNth(2) will need to return 8, and NOT 2, as your question describes.
But I can’t know for sure, and if so, I think you have enough tools to solve this issue without any problems!

Good luck

---

EDIT 2: After discussing in the comments, it is clear that the OP wanted something a little different than what the original question describes, so therefore additional editing:

Your solution searches for the item and returns it, perhaps what you want to do is COUNT, until that item, and then returns, should be something like this [again, without declaring all the variables, it won’t compile, it’s just direction]:

 template <class Type> Type getNth(stack(Type) & s, int n) { if(s.empty()) {return -1; } //note that in C++ throwing an exception here will be more wise, since -1 might be not matching to Type else if(n == 0) { return s.top(); } else { temp = s.pop(); retVal = getNth(s, n-1); s.push(temp); return retVal; } }