semantically recursive reverse string return statement

Question

현재 저는 재귀에 익숙해지고 더 많은 이해를 얻으려고 문자열을 뒤집는 것과 관련하여 그것을보고 싶었습니다. 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 

그러나 (부분).

미리 감사드립니다.

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

Answer 1

성명은 "지난 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" 

Answer 2

재귀의 경우 기본 사례와 재귀 호출을 고려할 때 가장 좋습니다.

이

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

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

끝에 반환 호출 그냥 문자열에서 첫 번째 문자를 복용하고 reverse의 재귀 호출에 합치된다

난 당신 같은 뭔가를 가정합니다. 점진적으로 짧은 문자열의 첫 번째 문자는 항상 문자열의 끝에 추가됩니다.

재귀의 각 단계를 생각하는 대신 기본 사례와 재귀 호출을 살펴 보는 것이 가장 좋습니다. 유도 과정을 사용하면 재귀가 작동하는지 확인할 수 있습니다.

실제로이 경우 3 자 (예 : "str")로 시작하는 문자열로 시작하는 것이 더 쉬울 것이라고 생각합니다. 그것이 작동하는 경우 모든 경우에 작동합니다 (유도입니다).