title: longest common subsequence java (recursive)
body: <p>The problem I'm working on is here:
  <a href="http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence" rel="nofollow noreferrer">http://practiceit.cs.washington.edu/problem/view/cs2/sections/recursivebacktracking/longestCommonSubsequence</a></p>
  
  <p>basically we are given two strings and we are requested to find the longest common subsequence. I've searched for solutions online and compared them to my own solution, and I couldn't find any bugs in my code. I wonder why it still wouldn't work.</p>
  
  <p>And also, I was requested to solve this problem by using recursive methods</p>
  
  <p>Here's my code:</p>
  
  <pre><code>public static String longestCommonSubsequence(String a, String b){
      if(a.isEmpty() || b.isEmpty()){
          return "";
      }
      if (a.substring(a.length() - 1).equals(b.substring(b.length() - 1))){
          return longestCommonSubsequence(a.substring(0, a.length() - 1), b.substring(0, b.length()
                         - 1)) + a.substring(a.length() - 1);
      } else {
          String first = longestCommonSubsequence(a, b.substring(b.length() - 1));
          String second = longestCommonSubsequence(a.substring(a.length() - 1), b);
          if(first.length() &gt; second.length()){
              return first;
          }
          return second;
      }
  }
  </code></pre>
  
  <p>And here are all the test cases:</p>
  
  <p>Call                                     Value Returned</p>
  
  <p>"ABCDEFG", "BGCEHAF"                       "BCEF"</p>
  
  <p>"she sells", "seashells"                   "sesells"</p>
  
  <p>"12345", "54321 21 54321"                  "123"</p>
  
  <p>"supercilious teacher", "delicious peach"  "ecious each"</p>
  
  <p>"Marty", "Helene"                          ""</p>
  
  <p>"","Joe"                                   ""</p>
  
  <p>"Suzy", ""                                 ""</p>
  
  <p>"ACGGTGTCGTGCTA", "CGTTCGGCTATCGTACGT"     "CGGTTCGTGT"</p>
  
  <p>with my code I got StackOverFlow for all the test cases.</p>