数据结构-递归（一）

数据结构-递归（一）

定义：

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

递归遍历链表的例子：

1
2
3
4
5
void f(Node node) {
    if(node == nu11){
        return;
    f(node.next);
}

说明:

  • 自己调用自己，如果说每个函数对应着一种解决方案，自己调用自己意味着解决方案是一样的(有规律的)

  • 每次调用，函数处理的数据会较上次缩减(子集)，而且最后会缩减至无需继续递归

  • 内层函数调用(子集处理)完成，外层函数才能算调用完成

思路：

  • 确定能否使用递归求解

  • 推导出递推关系，即父问题与子问题的关系，以及递归的结束条件

先递后归

例1：阶乘

1
2
3
4
5
private static int factorial(int n) {
    if (n == 0)
        return 1;
    return n * factorial(n - 1);
}

例2：倒序字符串

1
2
3
4
5
private static void reversePrint(String str) {
    if (str.isEmpty()) return;
    System.out.println(str.charAt(str.length()-1));
    reversePrint(str.substring(0, str.length()-1));
}

例3：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static int recursion(int[] arr, int target) {
    return recursionMain(arr, target, 0, arr.length - 1);
}

private static int recursionMain(int[] arr, int target, int i, int j) {
    if (i > j) return -1;

    int mid = (i + j) >>> 1;

    if (target < arr[mid]) {
        return recursionMain(arr, target, i, mid - 1);
    } else if (arr[mid] < target) {
        return recursionMain(arr, target, mid + 1, j);
    } else {
        return mid;
    }
}

例四：冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static int[] bubbleMain(int[] arr, int j) {
    if (j == 0) {
        return arr;
    }
    int x = 0;//用于记录i交换的位置
    for (int i = 0; i < j; i++) {
        if (arr[i] > arr[i + 1]) {
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
            x = i;
        }
    }
    //交换最终的位置作为边界，这样就不用进行后面多余的循环了
    bubbleMain(arr, x);
    return arr;
}

例五：插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void InsertionSortMain(int[] arr, int low) {
    // 如果待插入值已经在数组尾部之后，就说明排序结束
    if (low == arr.length) {
        return;
    }
    //获取待插入值
    int t = arr[low];
    //定义插入值将要比较位置的索引
    int i = low - 1;
    //如果发现比较值小于插入值，说明这一轮排序完成
    while (i >= 0 && arr[i] > t) {
        //如果比较值大于插入值，则比较值向右移动一位
        arr[i + 1] = arr[i];
        //继续向前比较
        i--;
    }
    //比较值小于插入值，就在比较值右边插入插入值，如果 i 为 -1，直接插入0索引，因此不用担心
    arr[i + 1] = t;
    //low 的值已经插入完成，现在拿起 low + 1 的值进行比较
    InsertionSortMain(arr, low + 1);
}
1
2
3
ps：如果插入值为 4
   [ 1 ,2 ,3, 5 ,5 ,6 ,7 ]
              ↑ 这是插入位置，因为上一轮 arr [ i + 1 ] = arr[ i ] ，因此无须担心会有数据丢失

例六：斐波那契数列第N个数的值

1
2
3
4
5
private static int f(int num) {
    if (num == 0) return 0;
    if (num == 1) return 1;
    return f(num - 1) + f(num - 2);
}

ps : 调用程序次数也是斐波那契数列，具体公式为：

1
2 * f(n + 1) - 1

时间复杂度：Θ = 1.618^n

code
#数据结构
数据结构-递归（一）
https://www.zheep.top/2024/11/30/数据结构-递归（一）/
作者
西行寺岩羊
发布于
2024年11月30日
许可协议