使用遞歸實(shí)現(xiàn)字符串逆序

以下代碼可以實(shí)現(xiàn)字符串逆序輸出：

/** 對字符串s進(jìn)行逆序，比如abcde逆序后為edcba */
public String reverse(String s) {
    return s.length() > 0 ? reverse(s.substring(1)) + s.charAt(0) : "";
}

比如執(zhí)行方法reverse("abcde");，會(huì)返回結(jié)果edcba。

怎么理解這個(gè)方法呢？

為了便于理解，我們把以上方法進(jìn)行單行改造，改造后的造價(jià)方法如下：

/** 對字符串s進(jìn)行逆序，比如abcde逆序后為edcba */
public static String reverse(String s) {
    boolean isNotEmpty = s.length() > 0;
    if (isNotEmpty) {
        String substring = s.substring(1);
        String reverse = reverse(substring);
        String result = reverse + s.charAt(0);
        return result;
    }
    return "";
}

然后對發(fā)造后的方法打斷點(diǎn)進(jìn)行Debug，即可弄清遞歸方法的執(zhí)行流程。

比如執(zhí)行reverse("abcde")，具體執(zhí)行流程如下：

// 首先依次執(zhí)行如下5個(gè)步驟，即方法遞歸了5次
1. substring("abcde");
2. substring("bcde");
3. substring("cde");
4. substring("de");
5. substring("e");

// 執(zhí)行完以上5個(gè)步驟后，遞歸結(jié)束，方法開始返回，返回值依次為：
5. e
4. d
3. c
2. b
1. a

遞歸執(zhí)行流程總結(jié)：

1. 方法返回的順序是與方法執(zhí)行的順序倒過來的；

2. 即最后執(zhí)行的方法，最先返回，最先執(zhí)行的方法，最后返回；

3. 遞歸方法執(zhí)行與返回的整個(gè)過程，類似于一個(gè)入棧和出棧的過程。

使用遞歸實(shí)現(xiàn)數(shù)組逆序

思路：從兩端向中間依次交換兩端位置的值，直到交換完畢。比如一個(gè)長度為6的數(shù)組，則交換過程如下：

0：5 交換0和5位置的元素
1：4 交換4和4位置的元素
2：3 交換2和3位置的元素
3：2 交換完畢，退出遞歸

/**
 * 使用遞歸實(shí)現(xiàn)數(shù)組倒序；
 * 依次交換以下位置元素的值：
 * 第1個(gè) 與 倒數(shù)第1個(gè)
 * 第2個(gè) 與 倒數(shù)第2個(gè)
 * 第3個(gè) 與 倒數(shù)第3個(gè)
 * ...
 */
public void reverseArray(int[] array, int start, int end) {
    // 依次交換兩端位置元素的值
    if (start < end) {
        int temp = array[end];
        array[end] = array[start];
        array[start] = temp;
        reverseArray(array, start + 1, end - 1);
    }
    // 順序交換完畢，輸出數(shù)組
    System.out.println(Arrays.toString(array));
}