递归--数据结构--黑马

递归

总结一句话，上手直接多刷Leetcode，比看这个更有用。

定义

递归是一种解决计算问题的方法，其中解决方案取决于同一类问题的更小子集。

例如，单链表递归遍历的例子：

void f(Node node) {if (node == null) {return;}f(node.next);
}

说明：

1. 自己调用自己，如果每个函数对应一个解决方案，自己调用自己意味着解决方案一样(有规律)。
2. 每次调用，函数处理的数据会较上次缩减（子集），而且最后会缩减至无需继续递归。
3. 内层函数调用（子集处理）完成，外层函数才能算调用完成。

例如，

// 假如链表是，1 -> 2 -> 3 -> null    
void f(Node node) {if (node == null) {return;}System.out.println("before: " + node.value);f(node.next);System.out.println("after: " + node.value);
}

根据递归的性质，从链表头节点开始遍历，打印第一个节点值 $node.value=1$ ，进入 $f(node.next)$ 第二个节点不为空，打印第二个节点值 $node.value=2$ ，进入 $f(node.next)$ 到第三个节点（不为null），打印第三个节点值 $node.value=3$ ，进入 $f(node.next)$ ，因为当前节点为null，则进入 $if$ 语句，return返回，执行第三次 $f$ 函数的输出语句，得到 $node.value=3$ ，然后执行第二次 $f$ 函数的输出语句，得到 $node.value=2$ ，最后执行第一次 $f$ 函数的输出语句，得到 $node.value=1$ 。

使用伪代码执行流程如下，不考虑语法正确。

// 假如链表是，1 -> 2 -> 3 -> null   
void f(Node node = 1) {System.out.println("before: " + node.value);			// 1void f(Node node = 2) {System.out.println("before: " + node.value);		// 2void f(Node node = 3) {System.out.println("before: " + node.value);	// 3void f(Node node = null) {if (node == null) {return;}}System.out.println("after: " + node.value);		// 3}System.out.println("after: " + node.value);			// 2}System.out.println("after: " + node.value);				// 1
}

简单应用

例1 - 阶乘

用递归方法求阶乘

• 阶乘定义：$n!=1\cdot 2\cdot 3\cdots (n-2)\cdot (n-1)\cdot n$ ，其中 $n$ 为自然数，$0!=1$ 。
• 递推关系

$$f(n)=\{\begin{array}{ll}1,& n=1\\ n\ast f(n-1),& n>1\end{array}$$

public class Factorial {public int f(int n) {if (n == 1) {return 1;}return n * f(n - 1);}
}

例2 - 递归反向打印字符串

public class ReversePrintString{public static void f(int n, String str) {if (n == str.length()) {		// 当n索引等于字符串长度，returnreturn;}f(n + 1, str);System.out.println(str.charAt(n));}public static void main(String[] args) {f(0, "abcd");}
}

例3 - 递归版二分查找

public class BinarySearch {public static int search(int[] a, int target) {return f(a, target, 0, a.length - 1);}// 实现递归的方法private static int f (int[] a, int target, int i, int j) {if (i > j) {// 递归终止条件，未找到return -1;}int m = (i + j) >>> 1;if (target < a[m]) {return f(a, target, i, m - 1);} else if (target > a[m]) {return f(a, target, m + 1, j);} else {return m;}}}

例4 - 递归版冒泡排序

public class BubbleSort{public static void sort (int[] a) {bubble(a, a.length - 1);}private static void bubble(int[] a, int j) {if (j == 0) {return;}for(int i = 0; i < j; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);}}bubble(a, j - 1);}public static void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}

递归版冒泡排序改进

public class BubbleSort{public static void sort (int[] a) {bubble(a, a.length - 1);}private static void bubble(int[] a, int j) {if (j == 0) {return;}int x = 0;		// 使用变量x记录下次排序的右边界for(int i = 0; i < j; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);x = i;}}bubble(a, x);}public static void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}
}

或者不使用递归，直接使用循环，如下

public class BubbleSort{public static void sort (int[] a) {int j = a.length - 1;while (true) {int x = 0;		// 使用变量x记录下次排序的右边界for(int i = 0; i < j; i++) {if (a[i] > a[i + 1]) {swap(a, i, i + 1);x = i;}}j = x;if (j == 0) {break;}}}public static void swap(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;}public static void main(String[] args) {int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};sort(arr);System.out.println(Arrays.toString(arr));}
}

例5 - 递归版插入排序

public class InsertionSort{public static void sort(int[] a) {insertion(a, 1);}public static void insertion(int[] a, int low) {if (low == a.length) {return;}int t = a[low];int i = low - 1;while (i >= 0 && a[i] > t) {a[i + 1] = a[i];i--;}if (low - 1 != i) {a[i + 1] = t;}insertion(a, low + 1);}}

不使用递归，直接使用循环，如下

public class InsertionSort{public static void sort(int[] a) {for(int low = 1; low < a.length; low++) {int t = a[low];			// 插入的值int i = low - 1;		// 已排序的右边界while (i >= 0 && a[i] > t) {a[i + 1] = a[i];i--;}// 找到插入点，找到比插入值小的索引if (low - 1 != i) {a[i + 1] = t;}}}
}

例6 - 斐波那契数列

递推关系

$$f(n)=\{\begin{array}{ll}0,& n=0\\ 1& n=1\\ f(n-1)+f(n-2),& n>1\end{array}$$

public class Fibonacci {public static int f(int n) {if (n == 0) {return 0;}if (n == 1) {return 1;}return f(n - 1) + f(n - 2);}
}

改进算法如下，使用空间换时间

public class Fibonacci {public static int fibonacci (int n) {int[] cache = new int[n + 1];Arrays.fill(cache, -1);cache[0] = 1;cache[1] = 1;return f(n, cache);}public static int f (int n, int[] cache) {if (cache[n] != -1) {return cache[n];} cache[n] = f(n - 1) + f(n - 2);return cache[n];}
}

递归时间复杂度计算

Master theorem 主定理

若有递归式
$$T(n)=aT(\frac{n}{b}+f(n))$$
其中

• $T(n)$ 是问题运行的时间，$n$ 是数据规模
• a 是子问题个数
• $T(\frac{n}{b})$ 子问题运行的时间，每个子问题被拆成原问题数据规模的 $\frac{n}{b}$
• $f(n)$ 是除去递归外运行的时间。

令 $x=lo{g}_{b}a$ ，即 $x=lo{g}_{子问题缩小倍数}$ 子问题个数

那么
$$T(n)=\{\begin{array}{ll}\Theta (n^x)& f(n)=O(n^c)并且c<x\\ \Theta (n^{x}logn)& f(n)=\Theta (n^x)\\ \Theta (n^c)& f(n)=\Omega (n^c)并且c>x\end{array}$$

例 1

$T(n)=2T(\frac{n}{2}+n^4)$

• $x=1<4$ ，由后者决定时间复杂度 $\Theta (n^4)$ 。

例 2

$T(n)=T(\frac{7n}{10}+n^4)$

• $x=0<1$ ，由后者决定时间复杂度 $\Theta (n)$ 。

例 3

$T(n)=16T(\frac{n}{4}+n^2)$

• $x=2=2$ ，由前者决定时间复杂度 $\Theta (n^{2}logn)$ 。

例 4 - 递归-二分查找

public static int f(int[] a, int target, int i, int j) {int m = (i + j) >>> 1;if (i > j) {return - 1;}if (target < a[m]) {return f(a, target, i, m - 1);} else if (target > a[m]) {return f(a, target, m + 1, j);} else {return m;}
}

• 子问题个数 $a=1$ ；
• 子问题数据规模缩小倍数 $b=2$ ；
• 除递归外执行的计算是常数级 $c=0$ ；

$T(n)=T(\frac{n}{2}+n^0)$

• 因为 $x=0=0$ ，时间复杂度为 $\Theta (logn)$ 。

例 5 - 递归-归并排序

// 伪代码
void split(B[], i, j, A[]) {if (j - i <= 1) {return;}m = (i + j) >>> 1;// 递归split(B[], i, m - 1, A[]);split(B[], m + 1, j, A[]);// 合并merge（B, i, m, j, A);
}

• 子问题个数 $a=2$ ；
• 子问题数据规模缩减倍数 $b=2$；
• 除递归外，主要时间花在合并上，用 $f(n)=n$ 表示；

$T(n)=2T(\frac{n}{2}+n)$

• 因为 $x=1=1$ ，时间复杂度为 $\Theta (nlogn)$ 。

展开定理

例 1 - 递归求和

long sum(long n) {if (n == 1) {return 1;}return sum(n - 1) + n;
}

$T(n)=T(n-1)+c$ ，$T(1)=c$

如下展开过程

$T(n)=T(n-2)+c+c$

$T(n)=T(n-3)+c+c+c$

$\cdots$

$T(n)=T(1)+(n-1)c=nc$

时间复杂度：$O(n)$

例 2 - 递归冒泡排序

void bubble(int[] a, int high) {if (high == 0) {return;}for(int i = 0; i < high; i++) {if (a[i] > a[i + 1]) {// 交换swap(a, i, i + 1);}}return bubble(a, high - 1);
}

$T(n)=T(n-1)+n$ ，$T(1)=c$

如下展开过程

$T(n)=T(n-2)+(n-1)+n$

$T(n)=T(n-3)+(n-1)+(n-2)+n$

$\cdots$

$T(n)=T(1)+2+\cdots +n=T(1)+(n-1)\frac{n+2}{2}=c+\frac{n^2}{2}+\frac{n}{2}-1$

时间复杂度：$O(n^2)$

推导公式网址

推导公式网址

多路递归

例 1-汉诺塔

public class HanoiTower{static LinkedList<Integer> a = new LinkedList<>();static LinkedList<Integer> b = new LinkedList<>();static LinkedList<Integer> c = new LinkedList<>();static void init(int n) {for (int i = n; i >= 1; i--) {a.addLast(i);}}// n 为圆盘个数// a, 源// b, 借// c, 目标static void move(int n, LinkedList<Integer> a, LinkedList<Integer> b, LinkedList<Integer> c) {if (n == 0) {return;}move(n - 1, a, c, b);			// 借助c盘，将a盘的n-1个移到b盘c.addLast(a.removeLast());		// 将a盘中的最后一个移到c盘move(n - 1, b, a, c);			// 借助a盘，将b盘的n-1个移动到c盘}public void print(){System.out.println("------------");System.out.println(a);System.out.println(b);System.out.println(c);}public static void main(String[] args) {// init(3);// print();			// a=[3, 2, 1], b=[], c=[]// b.addLast(a.removeLast());		// print();			// a=[3, 2], b=[1], c[]init(3);print();move(3, a, b, c);print();}
}

​ 使用展开定理，或者使用公式网址，子问题个数是2，数据规模比原来减少1，$T(n)=2T(n-1)+c$ ，中间操作（将a中的最后一个移动到c）看作常数 $c$ 。

例 2-杨辉三角

public class PascalTriangle {// 返回某个位置的值public static int element(int i, int j) {if (i == 0 || i == j) {return 1;}return element(i - 1, j - 1) + element(i - 1, j);}// 打印空格public void printSpace(int n, int i) {int num = (n - 1 - i) * 2;for(int j = 0; j < num; j++) {System.out.print(" ");}}// 打印前n行的杨辉三角public static void print(int n) {for(int i = 0; i < n; i++) {printSpace(n, i);for(int j = 0; j <= i; j++) {System.out.printf("-%4d", element(i, j)); 	// 左对齐，并占4位}System.out.print();		// 换行处理}}public static void main(String[] args) {print(5);}}

改进杨辉三角，使用二维数组记录已经计算过的每项元素

public class PascalTriangle {// 返回某个位置的值public static int element(int[][] triangle, int i, int j) {if (triangle[i][j] > 0) {return triangle[i][j];}if (i == 0 || i == j) {triangle[i][j] = 1;return 1;}triangle[i][j] = element(triangle, i - 1, j - 1) + element(triangle, i - 1, j)return triangle[i][j];}  // 打印前n行的杨辉三角public static void print(int n) {// 创建二维数组int[][] triangle = new int[n][];for(int i = 0; i < n; i++) {// 初始化每行i+1个元素triangle[i] = new int[i + 1];for(int j = 0; j <= i; j++) {System.out.printf("-%4d", element(triangle, i, j)); 	// 左对齐，并占4位}System.out.print();		// 换行处理}}public static void main(String[] args) {print(5);}}

改进杨辉三角，使用一维数组

public class PascalTriangle { public static void createRow(int[] row, int i) {if (i == 0) {row[0] = 1;return;}for(int j = i; j > 0; j--) {row[j] = row[j] + row[j - 1];}}// 打印前n行的杨辉三角public static void print(int n) {// 初始一维数组int[] triangle = new int[n];for(int i = 0; i < n; i++) {// 计算createRow(row, i);for(int j = 0; j <= i; j++) {System.out.printf("-%4d", element(triangle, i, j)); 	// 左对齐，并占4位}System.out.print();		// 换行处理}}public static void main(String[] args) {print(5);}}