Java 재귀(Recursion)란?

재귀함수란?

재귀의 사전적 의미는 '원래의 자리로 되돌아가거나 되돌아옴.' 이다. 정의를 참고하여 재귀를 코드로 표현한다면 다음과 같이 작성할 수 있을 것이다.

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

recursion 메서드를 호출하면 자기자신을 끝없이 호출하며 같은 코드가 계속해서 실행되는 것을 볼 수 있다. 이 recursion 메서드처럼 자기 자신을 호출하는 함수를 재귀함수라고 한다. 재귀함스를 잘 활용하면 반복적인 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.

재귀함수의 장점은,

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

반면, 단점으로는

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

재귀함수를 사용하기 위해서는 문제크기를 점점 작은 단위로 쪼갤 수 있어야 하며 재귀 호출이 종료되는 시점이 존재되어야 한다.

다양한 방식의 사고

재귀를 학슴하고 연습하며 하나의 문제를 해결하기위해 다양한 방식으로 생각하는 능력을 기를 필요가 있다. 아래의 문제를 해결해보자.

//자연수로 이루어진 리스트를 입력받고, 리스트의 합을 리턴하는 메서드 arrSum을 작성하자.

 

자연수로 이루어진 리스트의 합을 구하는 알고리즘으로, 보조변수 sum을 0으로 초기화 한 후 순차적으로 리스트 구성요소에 접근하며 sum에 더하는 반복문으로 아래와 같은 코드를 작성할 수 있다.

public int arrSum(int[] arr) {
  int sum = 0;
  for(int i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

 

재귀로 문제를 해결하기 위해 아래와 같은 단계를 따라 진행해보자.

1. 문제를 작게 쪼갠다.
2. 1번과 같은 방식으로 문제가 더 작아지지 않을 때까지 가장 작은 단위로 문제를 쪼갠다.
3. 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결한다.

반응형

1. 문제를 작게 쪼개기

우선 {1, 2, 3, 4, 5} 배열의 합을 구하는 과정을 구해보자. 단순하게 생각하면 {1, 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([])

 

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);
}

arrSum 메서드가 작동하는 방식을 시각적으로 확인해보자. arrSum 메서드가 내부에서 arrSum 메서드를 호출하면서 문제가 쪼개어져나가고, 결국 문제를 더 이상 쪼갤 수 없는 arrSum({}) 까지 메서드가 호출된다.

 

arr 조건문에 의해 더 이상 자기 자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다. 그 결과 중첩되어 있던 메서드들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.