語義理解遞歸反向字符串返回語句

目前，我熟悉遞歸和試圖達到進一步的理解，我想看看它在扭轉字符串的上下文中。我知道它並不像使用StringBuffer那樣高效，但就像我說的那樣，主要是爲了更好地理解。我知道在這方面有幾個關於這方面的問題，但我只想在演練中提供一些幫助。語義理解遞歸反向字符串返回語句

    return reverse(str.substring(1)) + str.charAt(0);

字符串在這種情況下=「開始」

我知道子方法走的是一條不子的第一個字符

遞歸調用。（部分）

reverse("Start") 
reverse("tart") 
reverse("art") 
reverse("rt") 
reverse("t") // when string is 1 char length then the reverse string is returned

但我想深入瞭解它如何在遞歸演練中連接和重新構建字符串。

在此先感謝。

來源

2011-08-28 L-Samuels

聲明

return reverse(str.substring(1)) + str.charAt(0);

在說「反向最後n-1個字符和第一字符移動到結束」（其中，所述串具有長度n）。這是有道理的，如果你認爲它跟蹤通過遞歸調用：

reverse("tart") + "S" 
(reverse("art") + "t") + "S" 
((reverse("rt") + "a") + "t") + "S" 
(((reverse("t") + "r") + "a") + "t") + "S" 
((((reverse("") + "t") + "r") + "a") + "t") + "S"

假設你離開的時候有一個空字符串一個合適的停車條件，方法調用現在會返回一個接一個：

(((("t") + "r") + "a") + "t") + "S" 
((("tr") + "a") + "t") + "S" 
(("tra") + "t") + "S" 
("trat") + "S" 
"tratS"

來源

2011-08-28 00:24:54

好的答案，但是當length（）是零（空字符串）時，我會一直返回空字符串。你不想測試一個空字符串。 – adamjmarkham

謝謝像素。那正是我需要的。豎起大拇指。 –

對於遞歸而言，最好根據基本情況和遞歸調用來思考。

我假設你有這樣的：

public String reverse(String str){ 
    if (str.length() == 0) 
     return str; 

    return reverse(str.substring(1)) + str.charAt(0); 
}

末返回調用剛剛從字符串採取的第一個字符，它串聯到reverse遞歸調用。所以逐漸變短的字符串的第一個字符總是被追加到字符串的末尾，即變爲顛倒。

而不是思考遞歸的每個階段，最好只看基本情況和遞歸調用。使用歸納過程可以確保遞歸可行。

事實上，我認爲在這種情況下，使用3個字符的字符串（例如「str」）來查看會發生什麼會更容易。如果它適用於所有情況（這是歸納）。

來源

2011-08-28 00:27:11 adamjmarkham

語義理解遞歸反向字符串返回語句

回答

相關問題