[Algorithm] 순환(recursion) 알고리즘(예제)

• 문자열을 프린트

public class Recursion {
    public static void main(String[] args) {
        printChars("abcdefg");
    }

    public static void printChars(String str) {
        if(str.length() == 0)
            return;
        else {
            System.out.println(str.charAt(0));
            printChars(str.substring(1));
        }
    }
}

 

• 문자열을 뒤집어 프린트

public class Recursion {
    public static void main(String[] args) {
        printCharsReverse("abcdefg");
    }

    public static void printCharsReverse(String str) {
        if(str.length() == 0)
            return;
        else {
            printCharsReverse(str.substring(1));
            System.out.println(str.charAt(0));
        }
    }
}

 

• 2진수로 변환하여 출력

public class Recursion {
    public static void main(String[] args) {
        printInBinary(16);
    }

    public static void printInBinary(int n) {
        if(n < 2)
            System.out.println(n);
        else {
            printInBinary(n/2);
            System.out.println(n%2);
        }
    }
}

 

• 배열의 합 구하기

public class Recursion {
    public static void main(String[] args) {
        int []data = {1, 3, 2};
        int n = data.length;
        System.out.println(sum(n, data));
    }

    public static int sum(int n, int []data) {
        if(n <= 0)
            return 0;
        else
            return sum(n-1, data) + data[n-1];
    }
}

 

• Recursion vs Iteration
  • 모든 순환함수는 반복문(iteration)으로 변경 가능
  • 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능함
  • 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 함
  • 하지만 함수 호출에 따른 오버해드가 있음(매개변수 전달, 액티베이션 프레임 생성 등)

 

• 순환 알고리즘 설계
  • 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
  • 모든 case는 결국 base case로 수렴해야 함
  • if(){return base case;} else {return recursion};
• 암시적(implicit) 매개변수를 사용하지 말고 명시적(explicit) 매개변수로 바꾸어라
  • 순차 탐색