코드스테이츠

[Section 2] 자료구조/알고리즘 - 재귀

강예은 2023. 3. 15. 00:47

재귀의 개념

재귀(再歸) : 원래의 자리로 되돌아가거나 되돌아옴.

재귀를 코드로 표현

public void recursion() {
  System.out.println("This is");
  System.out.println("recursion!");
  recursion();
}

[코드] 재귀의 코드 예시

메서드 호출

[그림] recursion 메서드의 호출 결과

 

자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것을 볼 수 있다. 이 recursion 메서드처럼 자기 자신을 호출하는 함수를 재귀 함수라고 한다.

재귀 함수의 장점

  • 불필요하게 여러 개의 반복문을 사용하지 않기 때문에 코드가 간결해지고, 수정이 용이
  • 변수를 여러 개 사용할 필요가 없음

 

재귀 함수의 단점

  • 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 힘듦
  • 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장. 이러한 과정은 반복문에 비해서 메모리를 더 많이 사용함
  • 메서드를 호출하고 매서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생

재귀 함수를 사용하기 위한 조건

  • 문제의 크기를 점점 작은 단위로 쪼갤 수 있어야 함
  • 재귀 호출이 종료되는 시점이 존재

 

재귀의 사용

문제를 작게 쪼개고 더 쪼갠 뒤 가장 작은 것을 해결하고, 그의 반복으로 큰 문제를 해결함

 

예시) 배열 [1, 2, 3, 4, 5] 의 합을 구하는 과정

 

1. 문제를 작게 쪼개기

단순하게 생각해보면, 배열의 합을 구할 때 [1, 2, 3, 4, 5] 의 합을 구하는 것보다 [2, 3, 4, 5] 의 합을 구하는 것이 더 작은 문제이고, 여기서 또 [2, 3, 4, 5] 의 합을 구하는 것보다 [3, 4, 5] 의 합을 구하는 것이 더 작은 문제

arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5])
...

 

2. 문제를 가장 작은 단위로 쪼개기

위에서 문제를 쪼갠 방식을 반복해서 문제를 계속해서 쪼개면 더 이상 쪼갤 수 없는 상태에 도달

...
arrSum([3, 4, 5]) == 3 + arrSum([4, 5])
arrSum([4, 5]) == 4 + arrSum([5])
arrSum([5]) == 5 + arrSum([])

마지막에는 arrSum 이 빈 배열을 받게 되면서 문제를 더 이상 쪼갤 수 없게 되었다

이로써 문제를 가장 작은 단위까지 쪼갰다

 

3. 문제 해결하기

가장 작은 단위의 문제를 해결. 문제를 쪼갤 때 같은 방식으로 쪼갰기 때문에, 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있다.

2번에서 도달한 가장 작은 문제는 arrSum([]) 빈 배열의 합은 0이므로, 0을 리턴

쪼개졌던 문제가 거꾸로 거슬러 올라가면서 합쳐지게 됩니다.

arrSum([]) == 0; // <-- 문제가 더는 작아지지 않는 순간
// 가장 작은 경우의 해결책을 적용합니다.
arrSum([5]) == 5 + arrSum([]) == 5 + 0 == 5;
arrSum([4, 5]) == 4 + arrSum([5]) == 4 + 5 == 9;
arrSum([3, 4, 5]) == 3 + arrSum([4, 5]) == 3 + 9 == 12;
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5]) == 2 + 12 == 14;
arrSum([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5]) == 1 + 14 == 15;

 

arrSum 메서드의 리턴값이 나오면서 연쇄적으로 문제가 해결되고, 최종적으로는 문제 전체가 해결

 

위 단계를 반영해서 arrSum 메서드를 완성

public int arrSum (int[] arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length == 0) {
    return 0;
  }

  int[] tail = Arrays.copyOfRange(arr, 1, arr.length);

  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr[0] + arrSum(tail);
}