Java Language
재귀

소개

비고

재귀의 기본 아이디어

재귀 란 무엇입니까?

일반적으로 재귀는 함수가 직접 또는 간접적으로 호출 할 때 발생합니다. 예 :

// This method calls itself "infinitely"
public void useless() {
    useless();  // method calls itself (directly)
}

문제에 대한 재귀 적용 조건 :

재귀 함수를 사용하여 특정 문제를 해결하기위한 두 가지 전제 조건이 있습니다.

1. 재귀의 끝점이 될 문제의 기본 조건이 있어야합니다. 재귀 함수가 기본 조건에 도달하면 더 이상 (더 깊은) 재귀 호출을하지 않습니다.

2. 재귀의 각 레벨은 작은 문제를 시도해야합니다. 따라서 재귀 함수는 문제를 더 작은 부분과 작은 부분으로 나눕니다. 문제가 유한하다고 가정하면 재귀가 종료됩니다.

Java에서는 세 번째 전제 조건이 있습니다. 문제를 해결하기 위해 너무 재발행 할 필요는 없습니다. 깊은 재귀는 Java에서 문제가 있음을 참조하십시오.

예

다음 함수는 재귀를 사용하여 계승을 계산합니다. 메소드 factorial 이 함수 내에서 자신을 어떻게 호출하는지 주목하십시오. 자신을 호출 할 때마다 매개 변수 n 을 1 씩 줄입니다. n 이 1 (기본 조건)에 도달하면 함수는 더 이상 반복되지 않습니다.

public int factorial(int n) {
    if (n <= 1) { // the base condition 
        return 1;
    } else {
        return n * factorial(n - 1);
    }
}

^{이는 정수 오버플로를 고려하지 않았거나 n 큰 값에 대해 호출 스택 오버 플로우 (예 : StackOverflowError 예외)를 고려하지 않았기 때문에 Java의 계승을 계산하는 실제 방법이 아닙니다.}

N 번째 피보나치 수 계산하기

다음 메서드는 재귀를 사용하여 N 번째 피보나치 수를 계산합니다.

public int fib(final int n) {
    if (n > 2) {
        return fib(n - 2) + fib(n - 1);
    }
    return 1;
}

이 메소드는 기본 케이스 (n <= 2)와 재귀 케이스 (n> 2)를 구현합니다. 이것은 재귀 관계를 계산하기 위해 재귀를 사용하는 것을 보여줍니다.

그러나이 예제는 설명하는 동안 비효율적입니다. 메서드의 각 단일 인스턴스는 함수 자체를 두 번 호출하여 N이 증가 할 때 함수가 호출되는 횟수가 기하 급수적으로 증가합니다. 위의 함수는 O (2 ^N )이지만 동일한 반복 솔루션은 복잡성 O (N)을 갖습니다. 또한 O (N) 부동 소수점 곱셈에서 평가할 수있는 "닫힌 형식"식이 있습니다.

1에서 N까지의 정수의 합계 계산

다음 메소드는 재귀를 사용하여 0에서 N까지의 정수의 합계를 계산합니다.

public int sum(final int n) {
    if (n > 0) {
        return n + sum(n - 1);
    } else {
        return n;
    }
}

이 방법은 O (N)이며 꼬리 호출 최적화를 사용하여 간단한 루프로 줄일 수 있습니다. 사실 O(1) 연산에서 합계를 계산하는 닫힌 형식 식이 있습니다.

숫자의 N 번째 힘 계산하기

다음 메소드는 재귀를 사용하여 exp 의 제곱으로 exp num 의 값을 계산합니다.

public long power(final int num, final int exp) {
    if (exp == 0) {
        return 1;
    }
    if (exp == 1) {
        return num;
    }
    return num * power(num, exp - 1);
}

이것은 위에서 언급 한 원칙을 설명합니다. 재귀 메소드는 재귀를 종료하는 기본 케이스 (n = 0과 n = 1 인 두 가지 경우)와 메소드를 다시 호출하는 재귀 케이스를 구현합니다. 이 방법은 O (N)이며 꼬리 호출 최적화를 사용하여 간단한 루프로 줄일 수 있습니다.

재귀를 사용하여 문자열 반전

다음은 문자열을 뒤집는 재귀 코드입니다.

/**
 * Just a snippet to explain the idea of recursion
 *
 **/

public class Reverse {
    public static void main (String args[]) {
        String string = "hello world";
        System.out.println(reverse(string)); //prints dlrow olleh
    }

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

재귀를 사용하여 트리 데이터 구조를 순회

아래처럼 3 개의 멤버 데이터, 왼쪽 자식 포인터, 오른쪽 자식 포인터를 가지는 Node 클래스를 고려하십시오.

public class Node {
    public int data;
    public Node left;
    public Node right;
    
    public Node(int data){
        this.data = data;
    }
}

아래처럼 여러 개의 Node 클래스의 객체를 연결하여 구성된 트리를 가로 질러 트래버스 할 수 있습니다. 트래버스는 트리의 순차 트래버스라고합니다.

public static void inOrderTraversal(Node root) {
        if (root != null) {          
            inOrderTraversal(root.left); // traverse left sub tree
            System.out.print(root.data + " "); // traverse current node
            inOrderTraversal(root.right); // traverse right sub tree
        }
    }

위에서 설명한 바와 같이 재귀 를 사용하면 반복적 인 접근 방법으로는 불가능한 다른 데이터 구조를 사용하지 않고 트리 데이터 구조 를 탐색 할 수 있습니다.

재귀 유형

재귀는 재귀 호출이 배치되는 위치에 따라 Head Recursion 또는 Tail Recursion 으로 분류 할 수 있습니다.

머리 재귀 에서 재귀 호출은 함수가 발생했을 때 함수의 다른 처리 (함수의 맨 위 또는 맨 앞에서 발생하는 것으로 생각) 전에 발생합니다.

꼬리 재귀 에서는 역순입니다. 재귀 호출 전에 처리가 발생합니다. 두 재귀 스타일 중 하나를 선택하는 것은 임의적으로 보일지 모르지만 선택이 모든 차이를 만들 수 있습니다.

경로의 시작 부분에 하나의 재귀 호출이있는 경로가있는 함수는 head recursion이라는 것을 사용합니다. 이전 전시회의 계승 함수는 머리 재귀를 사용합니다. 재귀가 필요하다고 판단되면 가장 먼저하는 일은 감소 된 매개 변수로 자신을 호출하는 것입니다. 경로 끝에 하나의 재귀 호출이있는 함수는 꼬리 재귀를 사용합니다.

public void tail(int n)              public void head(int n)
{                                       {
   if(n == 1)                             if(n == 0)
      return;                                return;
   else                                   else
      System.out.println(n);                 head(n-1);

   tail(n-1);                              System.out.println(n);
}                                        }

재귀 호출이 메서드의 끝에서 발생하면이를 tail recursion 라고합니다. 꼬리 재귀는 similar to a loop . 이 method executes all the statements before jumping into the next recursive call .

재귀 호출이 beginning of a method, it is called a head recursion 의 beginning of a method, it is called a head recursion 에서 발생 beginning of a method, it is called a head recursion . 이 method saves the state before jumping into the next recursive call .

참조 : 머리 및 꼬리 재귀 간의 차이점

StackOverflowError 및 루프 재귀

재귀 호출이 너무 깊어지면 StackOverflowError 합니다. Java는 스레드의 스택에서 모든 메소드 호출에 대해 새 프레임을 할당합니다. 그러나 각 스레드 스택의 공간은 제한적입니다. 스택의 프레임이 너무 많으면 스택 오버플로 (SO)가 발생합니다.

예

public static void recursion(int depth) {
    if (depth > 0) {
        recursion(depth-1);
    }
}

큰 매개 변수 (예 : recursion(50000) 로이 메서드를 호출하면 스택 오버플로가 발생할 수 있습니다. 정확한 값은 스레드 구성, 스레드 구성, -Xss 와 같은 명령 줄 매개 변수 또는 JVM의 기본 크기

해결 방법

재귀 호출은 데이터 구조에 각 재귀 호출의 데이터를 저장하여 루프로 변환 할 수 있습니다. 이 데이터 구조는 스레드 스택이 아닌 힙에 저장 될 수 있습니다.

일반적으로 메서드 호출의 상태를 복원하는 데 필요한 데이터는 스택에 저장 될 수 있으며 while 루프는 재귀 호출을 "시뮬레이트"하는 데 사용될 수 있습니다. 필요한 데이터는 다음과 같습니다.

• 메소드가 불려 간 객체 (인스턴스 메소드 만)
• 메소드 파라미터
• 지역 변수
• 실행 또는 메소드의 현재 위치

예

다음 클래스는 지정된 깊이까지 인쇄하는 트리 구조를 재귀 적으로 허용합니다.

public class Node {

    public int data;
    public Node left;
    public Node right;

    public Node(int data) {
        this(data, null, null);
    }

    public Node(int data, Node left, Node right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public void print(final int maxDepth) {
        if (maxDepth <= 0) {
            System.out.print("(...)");
        } else {
            System.out.print("(");
            if (left != null) {
                left.print(maxDepth-1);
            }
            System.out.print(data);
            if (right != null) {
                right.print(maxDepth-1);
            }
            System.out.print(")");
        }
    }

}

예

Node n = new Node(10, new Node(20, new Node(50), new Node(1)), new Node(30, new Node(42), null));
n.print(2);
System.out.println();

인쇄물

(((...)20(...))10((...)30))

이것은 다음 루프로 변환 될 수 있습니다 :

public class Frame {

    public final Node node;

    // 0: before printing anything
    // 1: before printing data
    // 2: before printing ")"
    public int state = 0;
    public final int maxDepth;

    public Frame(Node node, int maxDepth) {
        this.node = node;
        this.maxDepth = maxDepth;
    }

}

List<Frame> stack = new ArrayList<>();
stack.add(new Frame(n, 2)); // first frame = initial call

while (!stack.isEmpty()) {
    // get topmost stack element
    int index = stack.size() - 1;
    Frame frame = stack.get(index); // get topmost frame
    if (frame.maxDepth <= 0) {
        // termial case (too deep)
        System.out.print("(...)");
        stack.remove(index); // drop frame
    } else {
        switch (frame.state) {
            case 0:
                frame.state++;

                // do everything done before the first recursive call
                System.out.print("(");
                if (frame.node.left != null) {
                    // add new frame (recursive call to left and stop)
                    stack.add(new Frame(frame.node.left, frame.maxDepth - 1));
                    break;
                }
            case 1:
                frame.state++;

                // do everything done before the second recursive call
                System.out.print(frame.node.data);
                if (frame.node.right != null) {
                    // add new frame (recursive call to right and stop)
                    stack.add(new Frame(frame.node.right, frame.maxDepth - 1));
                    break;
                }
            case 2:
                // do everything after the second recursive call & drop frame
                System.out.print(")");
                stack.remove(index);
        }
    }
}
System.out.println();

참고 : 이것은 일반적인 접근법의 예일뿐입니다. 종종 프레임을 표현하고 /하거나 프레임 데이터를 저장하는 훨씬 더 좋은 방법을 생각해 낼 수 있습니다.

깊은 재귀는 Java에서 문제가된다.

재귀를 사용하여 두 개의 양수를 추가하는 다음 순진한 방법을 고려하십시오.

public static int add(int a, int b) {
    if (a == 0) {
        return b;
    } else {
        return add(a - 1, b + 1);  // TAIL CALL
    }
}

이는 알고리즘 적으로는 올바르지 만 큰 문제가 있습니다. 큰 a 가진 add 를 호출하면 StackOverflowError , 적어도 Java 9 이상의 Java 버전에서 충돌합니다.

일반적인 함수형 프로그래밍 언어 (및 다른 많은 언어)에서는 컴파일러가 꼬리 재귀를 최적화합니다. 컴파일러는 add (태그가 붙은 줄에서) 호출 이 꼬리 호출 이며 효과적으로 재귀를 루프로 다시 작성한다는 것을 알 수 있습니다. 이러한 변형을 꼬리 끌기 제거 (tail-call elimination)라고합니다.

그러나 현재의 Java 컴파일러는 테일 콜 제거를 수행하지 않습니다. (이것에 대한 기술적 인 이유는 간단 합니다만, 아래를 참조 해주세요.) 대신에 add 재귀 적으로 호출하면 (자), thread의 스택에 새로운 프레임이 할당됩니다. 예를 들어 add(1000, 1) 호출하면 1000 재귀 호출을 받아 1001 에 도달합니다.

문제는 스레드가 생성 될 때 Java 스레드 스택의 크기가 고정된다는 것입니다. (이것은 단일 스레드 프로그램의 "주"스레드를 포함합니다.) 너무 많은 스택 프레임이 할당되면 스택이 오버플로됩니다. JVM이이를 감지하고 StackOverflowError 시킵니다.

이 문제를 해결하기위한 한 가지 방법은 더 큰 스택을 사용하는 것입니다. 스택의 기본 크기를 제어하는 ​​JVM 옵션이 있으며 스택 크기를 Thread 생성자 매개 변수로 지정할 수도 있습니다. 불행히도 이것은 스택 오버플로를 "끕니다". 더 큰 스택이 필요한 계산을해야한다면 StackOverflowError 가 다시 발생합니다.

실제 솔루션은 심층 재귀가 발생할 가능성이 높은 재귀 알고리즘을 식별하고 소스 코드 수준에서 수동으로 꼬리 - 호출 최적화를 수행하는 것입니다. 예를 들어 add 메서드는 다음과 같이 다시 작성할 수 있습니다.

public static int add(int a, int b) {
    while (a != 0) {
       a = a - 1;
       b = b + 1;
    }
    return b;
}

(분명히 두 개의 정수를 더하는 더 좋은 방법이 있습니다. 위의 내용은 수동 테일 콜 제거의 효과를 설명하기위한 것입니다.)

왜 테일 콜 제거가 Java에서 구현되지 않는지 (아직)

Java에 꼬리 호출 제거를 추가하는 것이 쉬운 일이 아닌 데에는 여러 가지 이유가 있습니다. 예 :

• 어떤 코드는 StackOverflowError 에 의존하여 (예를 들어) 계산상의 문제의 크기에 경계를 둘 수 있습니다.
• 샌드 박스 보안 관리자는 권한이없는 코드가 권한있는 작업을 수행 할 수 있는지 여부를 결정할 때 종종 호출 스택을 분석합니다.

John Rose가 "VM의 Tail 호출" 에서 설명하는 것처럼

"호출자의 스택 프레임을 제거하는 효과는 액세스 제어 검사 및 스택 추적과 같은 일부 API에서 볼 수 있습니다. 호출자의 호출자가 호출 수신자를 직접 호출 한 것과 같습니다. 호출자가 소유 한 권한은 제어가 그러나 callee 메서드의 연결과 액세스 가능성은 컨트롤을 전송하기 전에 계산되며 꼬리 호출 호출자를 고려합니다. "

다시 말하자면, 꼬리 호출 제거 ​​(tail-call elimination)는 액세스 제어 메소드가 보안에 민감한 API가 신뢰할 수있는 코드에 의해 호출되었다고 잘못 생각할 수 있습니다.