자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ]

재귀(Recursion)란 컴퓨터 과학에서 자신을 정의할 때 자기 자신을 재참조하는 방식을 뜻하며 프로그래밍에 적용한 재귀 호출(Recursive call)의 형태로 많이 사용된다.

 

1) 순환적 특성이 존재해야 한다.

2) 순환을 종료할 중단 조건이 있어야 한다.

// ex 1)
public void A(...) {
    if(중단 조건) {
    
    }
    A(...);
}


// ex 2)
public void A() {
    if(중단 조건) {

    }
    B();
}

public void B() {
    if(중단 조건) {

    }
    A();
}

// 반복문
public static void evenNumber() {
    for (int i = 1; i <= 10; i++) {
        if (i % 2 == 0) {
            System.out.println(i);
        }
    }
}

// 재귀 함수
public static void evenNumber(int i) {
    if(i > 10) {
        return;
    } else if (i % 2 == 0) {
        System.out.println(i);
    }
    evenNumber(i + 1);
}

 

 

---

1. 점화식 관점

1) 시그마 (반복 순차 방식)

중단조건 : n이 5를 초과하면 중단

public static int f(int n) {
    return n;
}

public static int sigma(int n, int sum) {
    if (5 < n) {
        return sum;
    }
    int nextSum = (1 == n) ? f(n) : sum + f(n);
    return sigma(n + 1, nextSum);
}

System.out.println(simga(1, 1));

 

---

2) 공의 이동 거리 (반복 순차 방식)

위에서 공을 떨어트렸을 때 공의 높이가 1 미만이 될 때까지 공의 이동 거리의 총합을 구해야 할 때

(공은 한 번 튕겨저 나올 때마다 높이는 절반으로 줄어듦)

public static int sum(int h, int prevSum) {
    if (1 > h) {
        return prevSum;
    }
    int an = (prevSum == 0) ? h : h * 2;
    int sum = prevSum + an;
    return sum(h / 2, sum);
}

System.out.println(sum(16, 0));

 

 

---

3) 피보나치수열 (반복 순차 방식)

피보나치 수열은 첫 번째 항과 두 번째 항이 1이며 항과 이전 항의 합이 다음 항이 되는 수열

public static int fibonacci(int n, int twoPrevValue, int onePrevValue) {
    if (5 < n) {
        return onePrevValue;
    }
    int value = (1 == n || 2 == n) ? 1 : twoPrevValue + onePrevValue;
    return fibonacci(n + 1, onePrevValue, value);
}

System.out.println(fibonacci(1, 1, 1));

 

 

---

4) 피보나치수열 (분할 병합 방식)

public static int fibonacci(int n) {
    if (1 == n || 2 == n) {
        return 1;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

System.out.println(fibonacci(5));

 

 

---

2. 분할 관점

1) 배열의 값 더하기

- 분할 방식 : 중앙값 = (앞 인덱스 + 마지막 인덱스) / 2

- 중단 조건 : startIndex == endIndex

 

public static int sum(int[] arr, int startIndex, int endIndex) {
    if (startIndex == endIndex) {
        return arr[startIndex];
    }
    int middleIndex = (startIndex + endIndex) / 2;
    return sum(arr, startIndex, middleIndex) + sum(arr, middleIndex + 1, endIndex);
}

int[] arr = {4, 2, 5, 1, 5, 3, 1, 2};
int result = sum(arr, 0, arr.length - 1);

 

 

---

2) 최대값 구하기

public static int max(int[] arr, int startIndex, int endIndex) {
    if (startIndex == endIndex) {
        return arr[startIndex];
    }
    int middleIndex = (startIndex + endIndex) / 2;
    int leftValue = max(arr, startIndex, middleIndex);
    int rightValue = max(arr, middleIndex + 1, endIndex);
    return Math.max(leftValue, rightValue);
}

int[] arr = {2, 1, 6, 7, 5, 8, 3, 4};
System.out.println(max(arr, 0, arr.length - 1));

 

 

---

3. 백트래킹 관점

재귀에서 백트래킹은 '퇴각 검색'이라고도 불리며, 재귀 호출 시 Stack Frame이 쌓이고 Pop 되는 스택의 특징을 이용하여 탐색 가능한 이전의 경우로 돌아가서 다시 탐색하는 것을 말한다. 이러한 기법은 조건이 만족하는 한 모든 경우의 수를 탐색한다. 

 

ex) 미로 탈출

 

중단 조건 

1. 벽이 존재하는 곳에 이동할 수 없다.
2. 미로를 넘어서 이동할 수 없다.
3. 방문했던 곳으로 이동하지 않는다.

ex) 좌로 이동 시 중단 조건 (우, 상, 하 도 마찬가지로 3가지의 중단 조건 있음)

 

• 길을 찾아 나서는 방법

move 메서드의 재귀적인 호출을 통해 스택에 Stack Frame을 쌓아 나가는 방식으로 이동한다. 우로 이동하는 메서드가 계속 호출되다가 이동할 수 없는 상황이 오면, 일단 해당 메서드는 중단되며 이전 메서드의 실행 흐름으로 돌아가 그다음 구문인 아래로 이동한느 메서드를 호출한다. 아래로 이동할 수 없는 상황이 오면 이전 메서드의 실행 흐름으로 돌아가 좌로 이동하는 메서드를 호출한다. 이렇게 우, 아래, 좌, 위 이동 메서드를 호출하면서 중단 조건을 만나면 이전 실행 흐름에서부터 시작하는 것을 '백트래킹' 이라고 한다.

 

 

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼