Java recursion longest common subsequence

In summary, Java recursion works similarly to other languages with the use of functional and type recursion. However, it is important to note that the Java Virtual Machine does not support tail recursion well, which can lead to memory issues when using recursive algorithms.
  • #1
physicsfun
11
0
can someone explain java recursion to me?
 
Last edited:
Technology news on Phys.org
  • #2
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...

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

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

For functions...

Code:
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).
 
  • #3
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.
 

1. What is recursion in Java?

Recursion in Java is a programming technique where a method calls itself to solve a problem. It is a powerful and elegant way to solve problems that can be broken down into smaller subproblems.

2. What is a longest common subsequence in Java?

A longest common subsequence (LCS) in Java is a sequence of characters that appear in the same order in two or more strings, but not necessarily consecutively. It is used to find the longest sequence of characters that are common between two or more strings.

3. How does recursion help in finding the longest common subsequence in Java?

Recursion helps in finding the longest common subsequence in Java by breaking down the problem into smaller subproblems. The LCS problem can be solved by comparing the last characters of the two strings and then recursively finding the LCS of the remaining strings.

4. Can you explain the base case in Java recursion for finding the longest common subsequence?

The base case in Java recursion for finding the longest common subsequence is when one or both of the strings become empty. In this case, the LCS is considered to be zero as there are no more characters to compare.

5. Is recursion the most efficient way to find the longest common subsequence in Java?

No, recursion may not be the most efficient way to find the longest common subsequence in Java. It can lead to stack overflow if the input strings are too long. Dynamic programming is a more efficient approach for solving the LCS problem in Java.

Similar threads

  • Programming and Computer Science
Replies
5
Views
1K
  • Programming and Computer Science
Replies
2
Views
795
  • Programming and Computer Science
Replies
2
Views
1K
  • Programming and Computer Science
Replies
8
Views
1K
  • Programming and Computer Science
2
Replies
62
Views
10K
  • Programming and Computer Science
Replies
9
Views
1K
  • Programming and Computer Science
Replies
1
Views
2K
  • Programming and Computer Science
Replies
18
Views
1K
  • Programming and Computer Science
Replies
1
Views
953
  • Programming and Computer Science
2
Replies
39
Views
5K
Back
Top