公共子序列计算（递归方法）

公共子序列计算（递归方法）

首先是递归方法：

思路：首先定义两个指针，指向两字符串的索引0处，对两字符串从索引0处的值（字符型，charAt()方法）开始比较，如果相等，就将索引全部+1，并且返回值+1，即记此处有一个相同的字符。如果不相等，则有两个方向，分别是一个指针动，另一个指针不动。最终递归的出口是任意指针指向字符串末尾。则表示字符串遍历结束，返回0。

首先确定递归出口：如果任意指针指向字符串末尾。则表示字符串遍历结束，返回0。

递归条件：如果两指针指向位置的字符值相等，则指针全部+1，对后面的字符串继续比较。

如果指针处的值不相等，则有两个选择，分别是保持一个指针不动，另一个指针+1，并返回这两个方向中的最大值。（例如：字符串1：“abdca”；字符串2：“bbacd”;当指针都指向0时，比较0位置处的字符是否相等（'a' != 'b'），所以两个方向分别可以理解成 “abdca” 与 “bacd”  比较和  ”bdca”  与  “bbacd”相比较，取其中的最大值。然后继续向下递归。）

import java.util.*;
public class Main {
       public static void main(String[] args){
           Scanner sc = new Scanner(System.in);
           while(sc.hasNext()){
               String str1 = sc.nextLine(); 
               String str2 = sc.nextLine(); //获取两个字符串
               System.out.println(helper(str1,str2,0,0));
               
           }
       }
       public static int helper(String str1, String str2,int start1,int start2){
           if(start1 == str1.length()||start2 == str2.length())
               return 0;  
//递归出口：当两个指针其中一个指到其字符串的末尾是，表示后面没有数据，返回0
           if(str1.charAt(start1) == str2.charAt(start2))
               return helper(str1,str2,start1+1,start2+1)+1; 
//如果两指针所指向位置处的值相等，证明该处字符相等，则两指针都向后移一位，并且返回值+1表示该处字符相等,所以计数+1。
           else{
               return Math.max(helper(str1,str2,start1+1,start2),helper(str1,str2,start1,start2+1)); 
//如果值不相等，则分为两种情况，一种是字符串1指针向后一位，字符串2指针不动，另一种相反，所有情况都会包含在里面。
           }
       }
}