[자료구조] 재귀

재귀

재귀란 자신을 정의할 때 자기 자신을 재참조하는 방식을 의미하며, 프로그래밍에 적용한 Recursive call의 형태로 많이 사용된다. 재귀는 계속적으로 순환하기 때문에 이를 중단하는 조건 (기저 조건)이 반드시 있어야 한다.

재귀는 점화식, 분할, 백트래킹 관점에서 바라볼 수 있다.

점화식 관점

점화식 관점은 하나의 반복문으로 해결 가능한 반복 순차 방식과 하나의 반복문으로 해결하기 어려워 스택 구조의 특성을 이용하는 분할 병합 방식으로 나뉜다. 피보나치 값을 구하는 예제를 통해 점화식 관점을 살펴보자.

반복 순차 방식

public static int fibonacci(int n, int a, int b) {
  if (n > 5) return b;
  int value = (n==1 || n==2) ? 1 : a + b;
  return fibonacci(n+1, b, value);
}

분할 병합 방식

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

분할 관점

분할 관점은 분할-정복 알고리즘으로 큰 문제를 작은 단위로 쪼개어서 해결해나가는 것을 재귀적으로 풀어나가는 방식을 의미한다.

• 다음과 같이 배열의 합을 구할 때 분할해서 값을 구해보자.

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

• 다음과 같이 시작 인덱스, 종료인덱스, 중앙 값을 지정하여 재귀적으로 분할하여 계산할 수 있다.

백트래킹 관점

백트래킹은 퇴각 검색이라고 불리며 재귀 호출시 스택이 push 되고 pop되는 특징을 이용해서 탐색 가능한 이전의 경우로 돌아가서 탐색하는 것을 의미한다.

• 다음과 같이 미로를 탐색하는 문제를 해결한다면 다음과 같이 해결할 수 있다. 종료 조건으론 이동할 수 없는 경우, 출구를 찾은 경우를 지정하여 재귀를 종료할 수 있다.

private void move(int x, int y) {
  if (isFinished) {
    return;
  } else if (DEST_X == x && DEST_Y == y) {
    visit(x, y);
    isFinished = true;
    return;
  } else if (0 > x || 0 > y || x > mazeArray[y].length - 1 || y > mazeArray.length - 1) {
    return;
  } else if (WALL == mazeArray[y][x]) {
    return;
  } else if (mazeVisitArray[y][x]) {
    return;
  }

  visit(x, y);

  move(x + 1, y); // 오른쪽
  move(x, y + 1); // 아래
  move(x - 1, y); // 왼쪽
  move(x, y - 1); // 위
}

---

REFRENCES

https://www.codelatte.io/topics