递归问题

题目一

求 n!

实现代码如下：

public class Solution1{
    
    public static int getFactorial(int n){
        if(n == 0 || n == 1)
            return 1;
        
        return n * getFactorial(n - 1);
    }

}

题目二

汉诺塔问题
我们有从大到小放置的n个圆盘;
开始时所有圆盘都放在左边的柱子上;
按照汉诺塔游戏的要求我们要把所有的圆盘都移到右边的柱子上;
请实现一个函数打印最优移动轨迹。
给定一个int n，表示有n个圆盘。请返回一个string数组
其中的元素依次为每次移动的描述
描述格式为： move from [left/mid/right] to [left/mid/right]。

如果将汉诺塔问题中的left，mid，right三个杆子转换一个思路：
将left,mid,right三个具***置的杆转变为一种抽象的三个杆分别是from,to以及help杆。from杆指的是目前有圆盘想要将圆盘移动的杆，to指的是，想要将from杆上的圆盘移动至的目的地，help杆则是如果要遵守汉诺塔游戏的规则，则需要一个辅助杆，help的作用就是让from杆上的圆盘移动到to杆上面去的那个辅助杆。
N个圆盘在left杆上，现在如果想将left杆的N个圆盘都移动到right杆上，如果要是对left,mid,right三个杆的转移过程进行剖析则会非常麻烦，但是如果将N个圆盘转移的过程分解，就会分解成以下三个步骤：

将N-1个圆盘从from杆移动到help杆
将最后一个圆盘从from杆移动到to杆
将help杆上面的N-1个圆盘移动到to杆

实现代码如下：

import java.util.*;

public class Hanoi {
    
    ArrayList<String> strList = null;
    public ArrayList<String> getSolution(int n) {
      
        if(n <= 0)
            return null;
        
        strList = new ArrayList<>();
        process(n,"left","rigth","mid");    
        return strList;
        
    }
    
    private void process(int n,String from,String to,String help){
        if(n == 1){
            strList.add("move from " + from + " to " + to);
        }else{
            process(n - 1,from,help,to);
            strList.add("move from " + from + " to " + to);
            process(n - 1,help,to,from);
        }
    }
}

题目三

给定一个字符串，请打印出包括空字符串的所有子序列
例如字符串"ab"的所有子序列为："","a","b","ab"
字符串"abc"的所有子序列为："","a","b","c","ab","bc","ac","abc"

本题依旧可以使用递归的思路进行解决，具体思路如下：
对于字符串"abc"而言：

image.png

从空字符串开始出发，索引为0，走到“a”的时候有两种决策，第一个是和“a”合并第二个是不合并，一直走完这个字符串的长度，所有的子序列可能性全部都列出了。
实现代码如下：

public class PrintAllSubsequence{
    
    public static void printAllSubsequence(String str){
        if(str == null || str.length() == 0)
            return;
        char[] chars = str.toCharArray();
        process(chars,0,"");
    }
    
    public static void process(char[] chars,int index,String str){
        if(index == chars.length){
            System.out.println(str);
            return;
        }
        
        process(chars,index + 1,str);
        process(chars,index + 1,chars[index] + str);
    }
}

题目四

母牛生小牛问题
有一头母牛，它每年年初生一头小母牛。
每头小母牛从第四个年头开始，每年年初也生一头小母牛。
请编程实现在第n年的时候，共有多少头母牛？

分析过程如下：

image.png

前四年，第一年的母牛每年都会生出一只母牛，从第五年开始，前三年生出的母牛发育成熟可以生母牛，所以从第五年起，满足 f(n) = f(n - 1) + f(n - 3) 思路捋清楚后，代码实际上非常简单。

代码实现如下：

public class CowsProblem{
    
    public static int getCowsNum(int n){
        if(n == 1)
            return 1;
        
        if(n == 2)
            return 2;
        
        if(n == 3)
            return 3;
        
        if(n == 4)
            return 4;
        
        return getCowsNum(n - 1) + getCowsNum(n - 3);
    }
}

题目五

一个正整数的二维数组，二维数组中每个数都是正数
要求从左上角走到右下角，每一步只能向右或者向下。
沿途经过的数字要累加起来，返回最小的路径和。

分析：
对于矩阵：

因为只能从上往下走，从左往右走，所以如果要求出沿途经过数字累加的最小路径，可以用到暴力递归。当走到矩阵的右下角很显然返回，当走到了矩阵的最下面一行，行为就会变为只能从左向右走；当走到率矩阵最右边的一列，行为则会变为只能从上向下走，而对于既可以向右也可以向下走的时刻，我们只需要返回从右边走路径的和小还是从下面走路径的和小即可
本题目的解法属于暴力递归，相当于枚举出了所有可能出现的情况，所以并非是最优解。
代码实现如下：

public class MinPath{
    
    public static int getMinPath(int[][] matrix){
        if(matrix = null || matrix[0] == null)
            return 0;
        return process(matrix,0,0);
    }
    
    public static int process(int[][] matrix,int i,int j){
        if(i == matrix.length - 1 && j == matrix[0].length - 1){
            return matrix[i][j];
        }
        if(i == matrix.length - 1){
            return matrix[i][j] + process(matrix,i,j + 1);
        }
        if(j == matrix.length - 1){
            return matrix[i][j] + process(matrix,i + 1,j);
        }
        
        int rightWay = process(matrix,i,j + 1);
        int downWay = process(matrix,i + 1,j)
        return matrix[i][j] + Math.min(rightWay,downWay);
    }
}

题目六

一个正整数数组arr,和一个整数aim,如果可以任意选择arr中的数字，能不能累加得到aim
返回true或者false

这道题的思路和打印字符串所有的子序列的原理相似，我们也是从头遍历到数组的尾部，每次遇到数组的元素时，有两种决策，第一个是加上这个数字，第二个是不加这个数字；当走到数组的末尾时，返回累加的和是否和aim相等，我们可以看出，本题的思路也是暴力递归，如果动态规划分析本题会有更好的解法，本题的思路并非是最优解。
代码实现如下：

public class IsSum{
    
    public static boolean isSum(int[] arr,int aim){
        return isSumProcess(arr,0,0,aim);
    }
    
    public static boolean isSumProcess(int[] arr,int index,int sum,int aim){
        if(index == arr.length){
            return sum == aim;
        }
        return isSumProcess(arr,index + 1,sum,aim) || isSumProcess(arr,index + 1,arr[index] + sum,aim);
    }
}