Java Java recursion longest common subsequence

[physicsfun]

can someone explain java recursion to me?

 

[AUMathTutor]

I believe that recursion in Java works about the same as it does in most languages.

Basically, you have functional recursion and type recursion. Type recursion would be like a linked list. Functional recursion would be like a function calling itself. For instance...

class LinkedNode
{
   public int data;
   public LinkedNode next;
}

LinkedNode is a recursively defined type:
LinkedNode : null | int & LinkedNode.

For functions...

int factorial(int n)
{
   if(n<=0)
      return 1;
   else
      return n * factorial(n-1);
}

This is saying that factorial is 1 if n<=0, and n * factorial(n-1) otherwise (n > 0).

Basically, recursive definitions need a base case (null, n<=0) and a recursive part (some new information PLUS some (usually smaller) instance of the very same definition).

 

[Cantab Morgan]

Good insights, but Java has special concerns. Be warned that the Java Virtual Machine does not support tail recursion well. Consequently, recursive algorithms are more prone to "blow up the stack" by exhausting memory. This problem plagues all JVM languages, including Scala and Clojure, where recursion is heavily relied on.