title: Efficient way to do recursion with objects in Java?
body: <p>In dynamic programming using Java I frequently want to pass an array or object as a parameter in the recursive step. However, in order to have the original value be un-modified I would have to clone the object before passing it in as a parameter; by doing so I would have a very unfavorable time and space complexity since the method could have thousands of stacks. I read from <a href="https://stackoverflow.com/questions/45715068/is-there-a-more-efficient-way-passing-object-parameters-in-recursion">Is there a more efficient way passing object parameters in recursion?</a> that a possible method to overcome this problem could be by undoing the process after completing the computation. However, sometimes this is impossible to undo(for instance when the recursive method remove element(s) from the array). Does anyone have a solution to this problem? I am using this in the context of competitive programming and sometimes a bottom-up solution would be far too complex and impractical.</p>
  
  <p>An example:</p>
  
  <pre class="lang-java prettyprint-override"><code>public static int method(ArrayList&lt;Integer&gt; list) {
      if(list.size()==1) {
          return list.get(0);
      }
      ArrayList&lt;Integer&gt; clone = new ArrayList&lt;&gt;();
      for(int e:list) {
          clone.add(e);
      }
      clone.remove(clone.size()-1);
      method(clone);            
  }
  </code></pre>
  
  <p>If I did not clone it and did this instead:</p>
  
  <pre class="lang-java prettyprint-override"><code>public static int method(ArrayList&lt;Integer&gt; list){
      if(list.size()==1) {
          return list.get(0);
      }
      list.remove(list.size()-1);
      method(list);            
  }
  </code></pre>
  
  <p>the original object would be modified. In this case, one can obviously just return the first element of the array instead of creating this cuber-stone code. However, my point is to illustrate the problem of passing object.</p>