재귀 함수 짜는 법

재귀 함수 짜는 법

모든 반복문을 재귀 함수로 변환하는 것은 가능하지만, 이는 일반적으로 어려운 작업입니다. 그 이유는 재귀 함수의 사고 방식이 일반적인 인간의 사고 방식과 다소 다르기 때문입니다. 따라서 이를 습득하려면 충분한 연습과 익숙함이 필요합니다.

저는 이를 극복하기 위한것은 잘 반복문자체를 잘 정리하는 것이라고 생각해서 아래와 같은 표를 만들었습니다. 그리고 이를 바탕으로 쉬운 반복문부터 조금씩 어려운 반복문을 재귀함수로 구현하여, 나중에 이런 표없이 바로 구현하는것을 목표로 잡았습니다.

재귀함수 구현

• 목표:
• 종료 조건 (Base Case):
• 이전단계의 결과가 필요한가?:
• 문제분할 (Divide the Problem):
• 결과의 조합:
• 재귀호출, 다음 단계로 가기전 변경 할점 (Recursive Call):

연습 예제

Reverse a string 재귀함수 구현

• 목표: Reverse a string
• 종료 조건 (Base Case): 더 이상 뒤집을 문자가 없을 때 (즉, 문자열의 길이가 0이 될 때), If len(s) == 0: return s
• 이전단계의 결과가 필요한가?: Yes, 각 재귀 호출이 문자열의 나머지 부분을 뒤집습니다
• 문제분할 (Divide the Problem): 문자열의 첫 문자를 제외한 나머지 문자열을 뒤집는 것입니다, string - s[-1]
• 결과의 조합:stringbuilder sb.append s[-1]
• 재귀호출, 다음 단계로 가기전 변경 할점 (Recursive Call): 재귀 호출로 뒤집힌 나머지 문자열의 끝에 현재 문자를 추가하여 결과를 조합합니다,return reverse_string(s[1:], sb)

완성 코드

public static String reverseString(String input, StringBuilder sb){

        if(input.length()==0) return sb.toString();

        sb.append(input.charAt(input.length()-1));
        return reverseString(input.substring(0, input.length()-1),sb);
}

재귀함수 구현

• 목표: 팩토리얼
• 종료 조건 (Base Case):if n == 0 or n == 1: return 1
• 이전단계의 결과가 필요한가?: yes
• 문제분할 (Divide the Problem):factorial(input-1) * input
• 결과의 조합:factorial(input-1) * input
• 재귀호출, 다음 단계로 가기전 변경 할점 (Recursive Call): input-1

완성 코드

public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

public static int factorial(int n) {
        return factorialRecur(n, 1);
    }

    private static int factorialRecur(int n, int result) {
        if (n <= 1) {
            return result;
        }
        return factorialRecur(n - 1, n * result);
    }