title: Search a stack recursively, but leave the stack intact
body: <p>I have been trying to write a recursive function that searches a stack, but leaves the stack in its original state. I may pus
  h and pop the stack, but not use a helper stack or any other data stucture.</p>
  
  <p>And yes, this is homework, so I do not expect a complete coded answer :). A little help about how to approach the stack so that after the recursive search is finished the stack is intact would be appreciated.</p>
  
  <p>The recursive function that searches the stack for a specified item(but destroys the stack) is given below:</p>
  
  <pre><code>template &lt;class Type&gt;
  
  Type getNth(stack(Type) &amp; s, int n)
  
  {
  
      if(s.empty())
          return -1;
      if(s.top() == n)
          return s.top();
      if(s.top() != n &amp;&amp; s.empty())
          return -1;
      else
          s.pop();
          return getNth(s, n);
  }
  </code></pre>
  
  <p>This works, so far. 
  Any help greatly appreciated</p>