Java基础数据结构--递归

HanryLi

515人浏览 · 2026-03-21 18:11:08

HanryLi · 2026-03-21 18:11:08 发布

链表递归遍历

//递归遍历
    public void loop3(Consumer<Integer> before,
                      Consumer<Integer> after){
        recursion(head,before,after);
    }
    //递归函数
    //针对某个节点执行的操作
    private void recursion(Node curr,
                           Consumer<Integer> before, Consumer<Integer> after){
        if(curr!=null){
            return;
        }
        //System.out.println("before:"+curr.value);//正序
        before.accept(curr.value);
        recursion(curr.next, before, after);
        //System.out.println("after:"+curr.value);//逆序
        recursion(curr.next, before, after);
    }

这个代码依旧是函数式编程，我们可以发现在指向下一节点之前遍历链表和指向下一节点之后遍历链表顺序是反的

递归

自己调用自己,如果说每个函数对应着一种解决方案,自己调用自己意味着解决方案是一样的(有规律的)。每次调用,函数处理的数据会较上次缩减(子集),而且最后会缩减至无需继续递归。内层函数调用(子集处理)完成,外层函数才能算调用完成。用空间换时间

因此在链表递归遍历这个环节中 recursion(curr.next, before, after)就进入了下一节点； recursion(curr.next, before, after)就保留没有执行；直到运行到单项链表结尾，最后一个节点指向null，嵌套递归从内到外结束。所以递归之后遍历链表是逆序

深入到最里层叫做递；从最里层出来叫做归；在递的过程中,外层函数内的局部变量(以及方法参数)并未消失,归的时候还可以用到。因此使用递归时需要判断推到是否有递归关系以及结束条件

递归实操

阶乘

public class Factorial{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(f(n));
    }
    public int f(int n){
        if(n==1){
        return 1;
        }
        return n*f(n-1)
    }
}

反向打印字符串

//递归反向打印字符串

import java.util.Scanner;

public class ReversePrintString {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        String str=sc.nextLine();
        f(0,str);
    }
    public static void f(int n,String str){
        if(n==str.length()){
            return;
        }
        System.out.print(str.charAt(n));//顺序
        f(n+1,str);
        System.out.print(str.charAt(n));//逆序
    }
}

递归实现二分查找

public class E03BinarySearch {
    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 low,int high) {
        if(low>high) {
            return -1;
        }
        int m= (low+high) >>> 2;
        if (target < a[m]) {
            return f(a,target,low,m-1);
        }else if (a[m] > target) {
            return f(a,target,m+1,high);
        }else  {
            return m;
        }
    }
}

递归实现冒泡排序

/**
 *递归冒泡排序
 *将数组划分成两部分[0 .. j] [j+1 .. a.length-1]
 *左边[0 .. j]是未排序部分
 *右边[j+1 .. a.length-1]是已排序部分
 *未排序区间内,相邻的两个元素比较,如果前一个大于后一个,则交换位置
 */
public interface BubbleSort {
    public static void sort(int[] a){
        bubble(a,a.length-1);
    }
    //high 表示未排序区域的右边界
    private static void bubble(int[] a,int high){
        if(high==0){
            return;
        }
        for(int i=0;i<high;i++){
            if(a[i]>a[i+1]){
                int temp=a[i];
                a[i]=a[i+1];
                a[i+1]=temp;
            }
        }
        bubble(a,high-1);
    }
}

但是其实我们可以很简单的发现，在这个冒泡排序的递归调用中需要判断已经排好了的顺序是否还符合前小后大的规则，导致做了许多无用的比较因此，我们需要做出一点改动，我们用一个变量来记录：如果冒泡，前面的大数字与后面的小数字交换，这个变量记录原先大数字所在的位置索引。如果没有冒泡，这个变量不变。

最后这个变量所在的位置就是一轮冒泡最后一次交换前大数字的位置，而这个变量就是这轮冒泡之后无序(左侧)与有序(右侧)的分界线。这个就比先前的high-1作为边界要高明。

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

递归实现插入排序

public class InsertionSort {
    public static void sort(int[] a){
        insertion1(a,1);
    }
    //low 未排序区域的下届
    private static void insertion1(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--;
        }
        a[i+1]=t;

        insertion1(a,low+1);
    }
}

这个代码其实已经解决了插入排序的问题，但是我们发现这个程序一上来就把需要插入给存到t中，然后递归插入，可是如果这个待“插入”的元素不需要插入呢，这个元素比已排序区域的最大值还要大，直接赋值就有些鸡肋了，添加判断修改即可。

public class InsertionSort {
    public static void sort(int[] a) {
        insertion1(a, 1);
    }

    //low 未排序区域的下届
    private static void insertion1(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 (i + 1 != low) {
            a[i + 1] = t;
        }
        insertion1(a, low + 1);
    }
}

但是随之又有问题而来，我为了少这样的赋值操作，又在递归中实现许多次的判断。因此这个改进仅供参考。

还有另一个插入递归方法(但方法有更多赋值操作）

//另一种排序实现
    private static void insertion2(int[] a, int low) {
        if (low == a.length) {
            return;
        }

        int i  = low - 1;
        while (i >= 0 && a[i] > a[i+1]) {
            int t = a[i];
            a[i] = a[i+1];
            a[i+1] = t;

            i--;
        }

        insertion2(a, low + 1);
    }

多路递归

之前的例子是每个递归函数只包含一个自身的调用 single recursion

如果每个递归函数包含多个自身调用 multi recursion

斐波那契数列

F0	F1	F2	F3	F4	F5	F6	F7
0	1	1	2	3	5	8	13

简单实现

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

时间复杂度

调用递归次数

n=3	5
n=4	9
n=5	13

其实发现这个递归调用次数同样也是一个斐波那契数列，次数S(n)=2*f(n+1)-1,f(n)就是一般的斐波那契数列

递归

递归的优化(记忆法)

对于斐波那契数列，其实在编写过程中发现，多路递归时，有部分斐波那契数被多次使用，需要多次递归计算

public class Fibonacci {
    /**
     *使用Memoization(记忆法，也称备忘录)改进
     *
     * @param n-第n项
     * @return 第n项的值
     */
    public static int fibonacci(int n){
        int[] cache=new int[n+1];
        //初始化为负一
        Arrays.fill(cache,-1);
        if(n>=1){
            cache[0]=0;
            cache[1]=1;
        }
        return f(n,cache);
    }

    public static int f(int n,int[]  cache){
        if(cache[n]!=-1){
            return cache[n];
        }
        int x=f(n-1,cache);
        int y=f(n-2,cache);
        cache[n]=x+y;
        return cache[n];
    }
}

用一个数组来存储已经运算过了的斐波那契数，时间复杂度变为了O(n)，代价就是空间复杂度增加为O(n)

爆栈问题

简单运行一个递归求自然数前n项和的程序

/**
 * 递归求和
 *
 * n + n-1 + n-2 +...+ 1
 */
public class Sum {
    //f(n) = f(n-1) + n
    public static long sum(long n){
        if(n==1)return 1;
        return sum(n-1)+n;
    }

    public static void main(String[] args) {
        System.out.println(sum(15000));
    }
}

当我给定的数字达到一定大小后，竟然报错了StackOverflowError

在递归过程中，一层层递，一层层归，每次方法调用对应一个栈帧，栈由栈帧组成，爆栈。

尾调用

如果函数的最后一步是调用一个函数，那么就是尾调用

function a(){
function b()

}

以下三种则不能被称为尾调用

function a(){
const c = b()

return c

}

function a(){
return b() + 1//加法操作

}

function a(x){
return b() + x//加法操作

}

一些语言(C++/scala)的编译器能对尾调用做优化

function a(){
function b()

}

function b(){
function c()

}

function c(){
return 1000

}

a()

没优化之前的伪码

function a() {
        return function b() {
                return function c() {
                        return 1000

}

}

}

优化后的伪码

function a()
function b()
function c()

尾递归则是一种特殊的尾调用。当然Java中还是需要将递归改为循环来去解决爆栈问题

递归的时间复杂度

Master theorem主定理

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

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

辅助网站

并不是所有的递归均可以使用Master theorem主定理，因此在这介绍一个网站，只要我们能给出递推关系与一些条件，就可以得出时间复杂度--Wolfram|Alpha

多路递归实操

汉诺塔

对于汉诺塔来说，规则核心就两条：一次移动一个圆盘，小圆盘上不放大圆盘

而在操作过程中则是：把n-1个圆盘a->b；第n个圆盘a->c；n-1个圆盘b->c

public class HanoiTower {

    //三根柱子
    static LinkedList<Integer> a=new LinkedList();
    static LinkedList<Integer> b=new LinkedList();
    static LinkedList<Integer> c=new LinkedList();

    //底部 3>2>1 顶部
    static void init(int n){
        for(int i=n;i>=1;i--)
            a.addLast(i);
    }

    /**
     * @param n 圆盘个数
     * @param a 原始柱
     * @param b 中间柱
     * @param 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.addLast(a.removeLast());//中间
        print();
        move(n-1,b,a,c);
    }

    public static void main(String[] args) {
        init(3);
        print();
        move(3,a,b,c);
    }

    private static void print() {
        System.out.println("----------");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}

杨辉三角

虽然是三角形，但我们把它斜着来看

1 加8个空格

1 1                                      加6个空格

1 2 1   加4个空格

1 3 3 1   加2个空格

1 4 6 4 1        加0个空格

...... (n-1-i)*2

行i，列j [i][j]=[i-1][j-1]+[i-1][j]

j=0或i=j [i][j]=1

public class PascalTriangleV1 {
    /**
     *
     * @param i 行坐标
     * @param j 列坐标
     * @return
     */
    private static int element(int i,int j){
        if(j==0||i==j) return 1;
        return element(i-1,j-1)+element(i-1,j);
    }

    private static void printSpace(int n,int i){
        int num = (n-1-i)*2;
        for(int j=0;j<num;j++){
            System.out.print(" ");
        }
    }

    /**
     * @param 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));
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        print(5);
    }
}

初步代码已经给出，但是时间复杂度还是高的。其实我们发现这个递归运算中任然出现了许多次重复的计算，因此我们可以使用在斐波那契数列优化中使用的记忆法来优化

public class PascalTriangleV2 {
    /**
     *
     * @param triangle 二维数组
     * @param i 行坐标
     * @param j 列坐标
     * @return
     */
    private static int element(int[][] triangle,int i,int j){
        if(triangle[i][j]>0) return triangle[i][j];

        if(j==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];
    }

    /**
     * @param n 杨辉三角高度
     */
    public static void print(int n){
        int[][] triangle = new int[n][];
        for(int i=0;i<n;i++){
            triangle[i]=new int[i+1];
            for(int j=0;j<=i;j++){
                System.out.printf("%-4d",element(triangle,i,j));
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        print(6);
    }
}

但是二维数组也还是太麻烦了，用动态的一位数组去记录每一行，后一行还会覆盖前一行。递归就被优化了，变成一种迭代的形式

public class PascalTriangleV3 {
    /*
        0   0   0   0   0   0   初始状态
        1   0   0   0   0   0   i=0
        1   1   0   0   0   0   i=1
        1   2   1   0   0   0   i=2
        1   3   3   1   0   0   i=3
        1   4   6   4   1   0   i=4
        ......
     */
    private static void creatRow(int[] row,int i){
        if(i==0){
            row[0]=1;
            return;
        }
        for(int j=i;j>0;j--){
            row[j]=row[j-1]+row[j];
        }
    }

    public static void print(int n){
        int[] row = new int[n];
        for(int i=0;i<n;i++){
            creatRow(row,i);
            for(int j=0;j<=i;j++){
                System.out.printf("%-4d",row[j]);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        print(5);
    }
}

杨辉三角的编写还可以通过每一行的前一项计算出下一项,不必借助上一行,这与杨辉三角的另一个特性有关。同时也不难发现，杨辉三角的对称性这类诸多数学特性，这里暂不展开了