재귀적으로 작성하는 법

유방현·2022년 9월 19일

자료구조와 알고리즘

목록 보기

11/17

재귀 카테고리: 반복 실행

알고리즘 문제는 카테고리가 존재한다. 어떤 카테고리에 효과적인 기법을 터득하면 같은 카테고리에 속하는 문제를 해결 할 때 같은 기법을 적용 할수 있다.
    public static void countdown_recursive_(int num){
        System.out.println(num);
        if (num <= 0) return;
        countdown_recursive_(num-1);
        return;
    }
이 코드의 출력은 매번 다를 수 있으나, 코드의 본질은 숫자 출력 작업을 반복적으로 실행하는 것이다. 반복 실행 카테고리에 속하는 문제들은 함수의 마지막에 줄에서 단순히 그 함수를 다시 한 번 호출했다. 이 코드에서는 countdown_recursive_(num-1)이 이에 해당한다.
public static void findDirectory(File rootDir){
        File[] listAll = rootDir.listFiles();
        if (listAll == null) return;
        for (File file: listAll){
            if (file.isDirectory()){
                System.out.println("file = " + file);
                findDirectory(file);
            }
        }
    }
디렉토리에 있는 모든 디렉토리 명을 출력하는 코드가 있다. 이 또한 반복 실행 카테고리의 한 예이다. findDirectory(file)에서 재귀 함수를 다시 호출해 실행한다.

재귀 트릭: 추가 인자 넘기기

반복적으로 실행하는 카테고리의 문제 하나를 직접 풀어보자. 숫자 배열을 받아 배열 내 각 숫자를 두 배로 만드는 알고리즘을 작성한다. 단 새 배열을 만다는 것이 아니라 배열 자체에서 값을 수정한다. 이 알고리즘 또한 한 작업을 반복적으로 실행하는 카테고리에 속한다. 명확하게 말하면 반복적으로 숫자를 두 배로 만든다.
    public static void double_array(int[] arr, int n){
        if (arr.length <= n) return;
        arr[n] *= 2;
        double_array(arr,n+1);
        return;
    }
1. 우선 재귀 호출을 추가 한다.
2. 실제로 숫자를 두 배로 만드는 코드를 추가한다.arr[n] *= 2
3. 인덱스를 증가시키기 위해 인덱스를 기록할 변수를 인수로 받는다.double_array(int[] arr, int n)
4. 인덱스가 끝에 도달하면 멈춘다(기저 조건) .if (arr.length <= n) return

제자리 수정

일반적으로 데이터를 조작하는 기본적인 방법은 두 가지다. 첫 번째 방법은 실제 함수에 전달된 원본 배열은 그대로 두고 새 배열을 생성해 문제를 해결하는 것이다. 두 번 째 방법은 제자리 수정이라고 불린다. 실제 함수에 전달된 원본 배열을 바꾼다는 뜻이다.

재귀 카테고리: 계산

일반적은 카테고리인 하위 문제에 기반해 계산 수행하기를 해보자. 두 수의 합을 반환하는 함수나 배열에서 최댓값을 찾는 함수처럼 계산 수행이 목적인 함수가 많다. 이러한 함수는 입력을 받아 그 입력에 따른 계산 결과를 반환한다. 하위 문제를 정의하기 앞서 팩토리얼 문제를 생각해보자.
    public static int factorial(int num){
        if(num <= 1) return num;
        else return num * factorial(num - 1);
    }
factorial(6)은 factorial(5)*6이다. 즉 factorial(5)는 factorial(6)의 하위 문제이다. 하위 문제는 입력을 더 작게 한 똑같은 문제이다.
이 코드에서 return num * factorial(num - 1) num과 하위 문제factorial(num-1)을 계산한다.

두 가지 계산 방식

함수를 작성하는 방식은 두 가지다. 상향식으로 답을 찾아 갈 수 있고, 문제의 하위 문제에 기반해 계산함으로써 하향식으로 문제를 해결해 나갈 수 있다. 상향식과 하향식은 실제 컴퓨터 과학 교재에서 재귀 전략을 논할 떄 쓰인다.
팩토리얼 문제 또한 상향식 방식으로 해결 할수 있다.
    public static int factorial(int num, int i, int p){
        if(num < i) return num;
        else return num * factorial(num,i + 1, p * i);
    }
이렇게 구현 할 수 있으나, 그다지 간결하지 못하며 전형적인 루프에 비해 장점도 없다.
상향식에서는 루프를 쓰든 재귀를 쓰든 같은 전략으로 계산한다. 즉 계산 방식이 같다.
하지만 하향식에서는 재귀를 써야한다. 하향식 전략을 구현할 방법은 재귀 뿐이다.

하향식 재귀: 새로운 사고 방식

하향식 사고 방식은 문제를 해결하는 새로운 사고 전략을 제공한다. 즉 재귀적 하향식 방식은 문제를 완전히 다른 방식으로 생각하게 해준다. 구체적으롬 말해 하향식으로 풀떄 머릿속에서 문제를 뒤로 미루게 된다. 상향식으로 풀어 나갈 때 통상적으로 고려해야하는 문제의 본질에 세부적으로 파고들지 않아도 된다.
팩토리얼 문제는 하위 문제를 통해 문제를 해결한다. 그렇다면 호출 할 함수가 어떻게 동작하는지 코드를 작성할 때 알아야 할까? 엄밀히 말해 그렇지 않다. 다른 함수를 호출하는 코드를 작성 할 때는 호출 하는 함수가 어떻게 동작하는지 모르더라도 늘 그 함수가 올바른 값을 반환한다고 가정한다. 세부 사항은 하위 문제에서 다루게 두자.

하향식 사고 절차

1. 작성 중인 함수를 이미 누군가 구현해 놓았다고 가정하자.
2. 문제의 하위 문제를 찾자.
3. 하위 문제에 함수를 호출하면 어떻게 되는지 보고 거기서부터 시작하자.

배열 합

    public static int sum(ArrayList<Integer> arr){
        if (arr.size() == 1) return arr.get(0);
        return arr.get(0) + sum(new ArrayList<Integer>(arr.subList(1,arr.size())));
    }
[1,2,3,4,5]배열의 합은 15이다. 이 값은 인덱스 0 1 + [2,3,4,5]을 알 수 있다.
즉 이미 나머지 배열을 더 해주는 함수가 있다고 가정 하고 코드를 완성한다. 그 후 기저 조건을 추가한다.

문자열 뒤집기

    public static String reverse(String string){
        if (string.length() == 1) return String.valueOf(string.charAt(0));
        return reverse(string.substring(1,string.length())) + string.charAt(0);
    }

이 또한 마찬가지다 문자열을 뒤집기 위해서는 맨 첫 번째 문자열 맨 마지막에 더해주면 된다.

x세기

    public static int countX(String s){
        if (s.length() == 0) return 0;
        if(s.charAt(0) == 'x') return 1 + countX(s.substring(1,s.length()));
        else return countX(s.substring(1,s.length()));
    }
이 또한 비슷한다. 첫 문자가 x라면 1을 더 한다. 나머지 문자열에서 x를 세는 함수는 있다고 가정한다. 그 후 기저 조건을 추가한다.

계단 문제

주어진 계단이 있을 때 계단을 오르는 방법은 한칸, 두칸, 세칸이다. 그렇다면 계단의 길이가 N일 떄 몇 가지의 경우의 수를 가질 수 있을까??
이 때 하향식 재귀를 통해 문제를 해결하면 간단히 해결 할 수 있다.
    public static int numberOfPaths(int n){
        if (n < 0) return 0;
        if(n == 1 || n == 0) return 1;
        return numberOfPaths(n-1) + numberOfPaths(n - 2) + numberOfPaths(n - 3);
    }
결국 계단에 도착 했거나 1칸만 남는다면(1칸 오르기 때문) 경우 수가 하나 늘어난다. 이를 재귀로 생각하면 우선 주어진 계단에서 1,2,3을 뺀다 그 후 남은 계단에서 또 1,2,3을 뺀다. 이 때 남은 계단이 0 or 1이라면 경우의 수를 하나 늘린다. 얼마나 간단한가!!
이처럼 하향식 재귀 방식을 사용하면 다른 방식보다 훨씬 쉽게 문제를 해결 할 수 있다.

애너그램 생성

    public static ArrayList<String> anagramsOf(String alphabets){
        //기저 조건: 문자열 길이기 하나일 때 문자열을 리스트로 반환.
        if (alphabets.length() == 1) return new ArrayList<String>(Arrays.asList(alphabets));
        //문자열을 저장하기 위한 리스트.
        ArrayList<String> arrayList = new ArrayList<>();
        // 두번 쨰 문자부터 마지막 문자까지의 모든 애너그램을 찾는다. abcd라면 bcd의 애너그램을 찾는다.
        ArrayList<String> subAlphabets = (anagramsOf(alphabets.substring(1,alphabets.length())));
        //애너그램의 문자열을 저장하기 위해 생성.
        StringBuilder sb = new StringBuilder();
        // 찾은 부분 문자열을 리스트를 순회한다.
        for (int i = 0; i < subAlphabets.size(); i++){
            // 문자열 리스트의 문자열을 순회한다.
            for (int j = 0; j <= subAlphabets.get(i).length(); j++){
                // 문자열 저장한다.
                sb.append(subAlphabets.get(i));
                // 저장한 문자열에 모든 부분에 알파벳의 첫 문자를 삽입한다.
                sb.insert(j,alphabets.charAt(0));
                // 문자가 삽입된 문자열을 리스트에 저장한다.
                arrayList.add(sb.toString());
                // 리스트를 초기화 한다.
                sb.setLength(0);
            }
        }
        return arrayList;
    }