常见递归算法题目整理

)

一、单路递归

1、阶乘计算

public class 阶乘计算 {// 1*2*3....*100public static void main(String[] args) {System.out.println(num(10));}private static int num(int i) {if (i == 1 || i == 0) {return i;}return i * num(--i);}
}

2、翻转字符串

public class 翻转字符串 {public static void main(String[] args) {String str = "wrewtyu";f(str,0);}private static void f(String str, int index) {if (index == str.length()) {return;}f(str, index + 1);System.out.println(str.charAt(index));}
}

3、二分查找

public class 二分查找 {public static void main(String[] args) {int[] arr = {1, 2, 3, 5, 6, 7, 9, 22, 33, 66, 78, 81, 99, 100};int targetNum = 3;System.out.println(binarySearch(arr, targetNum, 0, arr.length));}private static int binarySearch(int[] arr, int targetNum, int left, int right) {if (left > right) {return -1;}int mid = (left + right) >>> 1;if (arr[mid] < targetNum) {return binarySearch(arr, targetNum, mid + 1, right);} else if (arr[mid] > targetNum) {return binarySearch(arr, targetNum, left, mid - 1);} else {return mid;}}
}

二、多路递归

1、斐波那契

1）基础版

public class FeiBoNaQieTest {public static void main(String[] args) {System.out.println(f(10));}private static int f(int n) {if (n == 1) {return 1;}if (n == 0) {return 0;}return f(n - 1) + f(n - 2);}
}

2）缓存版

基础版已经能够完成我们的目的，但是在计算每一项的时候会重复计算，比如在计算第8项和第9项的时候，都需要借助第7项，继而导致第7项重复计算。此处添加一个缓存数组cache，用于存放已经计算过的项，避免重复进行计算

public class FeiBoNaQieCacheTest {public static void main(String[] args) {int length = 18;// 1、将所有计算过的值缓存在数组中，避免重复计算int[] cache = new int[length + 1];// 2、默认都赋值为-1Arrays.fill(cache, -1);// 3、赋值前两项cache[0] = 0;cache[1] = 1;System.out.println(f(length, cache));}private static int f(int n, int[] cache) {if (cache[n] != -1) {// 曾经计算过return cache[n];}int i = f(n - 1, cache);int j = f(n - 2, cache);// 返回数据的同时将数据进行缓存cache[n] = i + j;return i + j;}
}

2、汉诺塔

public class HanNuotaTest {private static List<Integer> a = new LinkedList<>();private static List<Integer> b = new LinkedList<>();private static List<Integer> c = new LinkedList<>();public static void main(String[] args) {int n = 5;init(n);print();f(n, a, b, c);print();}/*** @param n 圆盘个数* @param a 源* @param b 借* @param c 目*/private static void f(int n, List<Integer> a,List<Integer> b,List<Integer> c) {if (n == 0) {return;}// 1、n个圆盘，将顶部n-1个圆盘，借助c，由a移动到bf(n - 1, a, c, b);// 2、将a移动到cInteger remove = a.remove(a.size() - 1);c.add(remove);// 如果是LinkedList，可以直接使用removeLast// c.add(a.removeLast());// 3、n个圆盘，将顶部n-1个圆盘，借助a，由b移动到cf(n - 1, b, a, c);}/*** 初始化汉诺塔集合** @param n 圆盘个数*/private static void init(int n) {for (int i = n; i > 0; i--) {a.add(i);}}/*** 打印哈诺塔内容*/private static void print() {System.out.println("---");System.out.println("a: " + a.toString());System.out.println("b: " + b.toString());System.out.println("c: " + c.toString());}
}

3、杨辉三角

1）基础版

public class YangHuiTest {public static void main(String[] args) {f(30);}/*** @param length 杨辉三角高度*/private static void f(int length) {if (length == 0) {return;}for (int i = 0; i < length; i++) {printSpace(length, i);for (int j = 0; j <= i; j++) {// 格式化打印元素占用位置宽度System.out.printf("%-4d", getElement(i, j));}System.out.println();}}/*** 打印每一行前面的空格，空格数与杨辉三角高度和元素位置有关系：（高度-1-位置下标）*2** @param length 杨辉三角高度* @param i      元素位置*/private static void printSpace(int length, int i) {int spaceNum = (length - 1 - i) * 2;for (int k = 0; k < spaceNum; k++) {// 这里与元素占用位置大小有关系（本demo为占用4个位置）System.out.print(" ");}}/*** 获取元素：(3,2)=(2,2)+(2,1)，两边元素（i,j）、(0,j)都是1** @param i 横坐标* @param j 纵坐标* @return (i, j)坐标元素*/private static int getElement(int i, int j) {if (j == 0 || i == j) {return 1;}return getElement(i - 1, j - 1) + getElement(i - 1, j);}
}

2）缓存版

此处的缓存做法与斐波那契做法相同，使用一个二维数组存储杨辉三角的各个元素，我们在使用getElement方法获取元素的时候，可以直接去二维数组中获取，继而减少递归计算的次数

public class YangHuiCacheTest {public static void main(String[] args) {f(30);}/*** @param length 杨辉三角高度*/private static void f(int length) {if (length == 0) {return;}// 初始化一个二维数组 用于缓存集合（直接length,length太浪费空间）int[][] cache = new int[length][];for (int i = 0; i < length; i++) {// 二维数组的每一行长度为i+1cache[i] = new int[i + 1];printSpace(length, i);for (int j = 0; j <= i; j++) {// 格式化打印元素占用位置宽度System.out.printf("%-4d", getElement(cache, i, j));}System.out.println();}}/*** 打印每一行前面的空格，空格数与杨辉三角高度和元素位置有关系：（高度-1-位置下标）*2** @param length 杨辉三角高度* @param i      元素位置*/private static void printSpace(int length, int i) {int spaceNum = (length - 1 - i) * 2;for (int k = 0; k < spaceNum; k++) {// 这里与元素占用位置大小有关系（本demo为占用4个位置）System.out.print(" ");}}/*** 获取元素：(3,2)=(2,2)+(2,1)，两边元素（i,j）、(0,j)都是1** @param i 横坐标* @param j 纵坐标* @return (i, j)坐标元素*/private static int getElement(int[][] cache, int i, int j) {if (cache[i][j] != 0) {return cache[i][j];}if (j == 0 || i == j) {cache[i][j] = 1;return 1;}cache[i][j] = getElement(cache, i - 1, j) + getElement(cache, i - 1, j - 1);return cache[i][j];}
}

3）优化缓存版

缓存版本将整个杨辉三角都进行了缓存，但是真实在计算的时候我们会发现，其实只需要缓存计算行的上一行数据即可，即以空间换时间的空间可以进行优化。此版本使用一个一级缓存进行缓存上一行的数据。

public class YangHuiCachePlusTest {public static void main(String[] args) {f(5);}/*** @param length 杨辉三角高度*/private static void f(int length) {if (length == 0) {return;}int[] row = new int[length];for (int i = 0; i < length; i++) {// 获取当前行。// 当前行的数据需要依赖row集合的数据，row集合的数据来源于上一次for循环赋值的结果createRow(row, i);// 二维数组的每一行长度为i+1printSpace(length, i);for (int j = 0; j <= i; j++) {// 格式化打印元素占用位置宽度System.out.printf("%-4d", row[j]);}System.out.println();}}/*** 打印每一行前面的空格，空格数与杨辉三角高度和元素位置有关系：（高度-1-位置下标）*2** @param length 杨辉三角高度* @param i      元素位置*/private static void printSpace(int length, int i) {int spaceNum = (length - 1 - i) * 2;for (int k = 0; k < spaceNum; k++) {// 这里与元素占用位置大小有关系（本demo为占用4个位置）System.out.print(" ");}}/*** 创建杨辉三角一行的数据*/private static void createRow(int[] row, int n) {if (n == 0) {row[0] = 1;return;}// 集合赋值只能由右往左赋值，从左往右i位置的值会被计算出来的新值覆盖for (int i = n; i > 0; i--) {row[i] = row[i] + row[i - 1];}}
}