코드 스테이츠

코드 스테이츠 - 재귀함수

한휘용 2023. 5. 10. 19:15
728x90

재귀 함수란?

 

재귀 함수는 자기 자신을 호출하는 함수를 말한다. 재귀 함수를 잘 활용하면 반복 작업을 해야하는 문제를 좀 더 간결한 코드로 풀어낼 수 있다.

 

재귀 함수의 장점

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

 

재귀 함수의 단점

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

 

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

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

 

 

재귀로 문제를 해결하는 단계

 

이론적으로 재귀로 문제를 해결할 때 거쳐야 하는 단계는 다음과 같다. 

  1. 문제를 작개 쪼개기
  2. 문제를 더 작게 가장 작은 단위로 쪼개기
  3. 가장 작은 단위의 문제를 해결함으로써 전체 문제를 해결하기

위 단계를 통해서 배열 [ 1, 2, 3, 4, 5]의 합을 구하는 과정을 재귀로 풀어보자.

 

 

1. 문제를 작게 쪼개기

 

먼저 배열 [1, 2, 3, 4, 5]의 합을 구하는 과정을 작게 쪼개야 한다.

단순하게 생각하면, 배열의 합을 구할 때 [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([1, 2, 3, 4, 5]) == 1 + arrSum([2, 3, 4, 5])
arrSum([2, 3, 4, 5]) == 2 + arrSum([3, 4, 5])
arrSum([3, 4, 5]) == 3 + arrSum([4, 5])
arrSum([4, 5]) == 4 + arrSum([5])
arrSum([5]) == 5 + arrSum([])

arrSum이 빈 배열을 박데 되면서 문제를 더 이상 쪼갤 수 없게 되었다. 이렇게 되면 문제를 가장 작은 단위까지 쪼갰다고 할 수 있다.

 

3. 문제 해결하기

 

문제가 더 쪼개지지 않게 되면, 가장 작은 단위의 문제를 해결한다. 문제를 쪼갤 때는 계속 같은 방식으로 쪼갰기 때문에, 가장 작은 단위의 문제를 해결한 방식으로 문제 전체를 해결할 수 있다.

 

가장 작은 단위로 쪼갠 문제는 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의 리턴값이 나오면서 문제가 해결되고, 최종적으로 구하고자 했던 배열[1, 2, 3, 4, 5]의 합이 도출되며 문제가 해결되는 것을 볼 수 있다.

 

위 단계를 반영한 메서드를 완성해보자.

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([]) 는 조건문에 의해 더 이상 자기 자신을 호출하지 않고, 숫자 0을 리턴하면서 종료된다.

그 결과 중첩되어 있던 메서드들도 연쇄적으로 숫자를 리턴하고, 최종적으로는 배열의 모든 요소의 합을 리턴하면서 문제가 해결된다.

 

 

반복문 VS 재귀

 

재귀를 사용하기 적합한 상황은 다음과 같다.

  1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우
  2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우
  3. 변수 사용을 줄여 mutable state(변경 가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

모든 재귀 함수는 반복문으로 표현할 수있다. ex) wihle 문 또는 for 문

그러나 재귀를 적용할 수 있는 대부분의 경우, 재귀를 적용한 코드가 더욱 간결하고 이해하기 쉽다.

 

 

재귀 함수의 동작 원리

 

Guide : 재귀적으로 사고하기

 

1. 재귀 함수의 입력값과 출력값 정의하기

 

재귀 함수를 통해 풀고자 하는 문제, 즉 도달해야 하는 목표를 정의하는데 도움이 된다. 재귀적으로 사고하는 데에 가장 먼저 해야 할 일은 문제를 가장 추상적으로 또는, 가장 단순하게 정의해야한다. 함수 arrSum의 경우 int 타입을 요소로 갖는 배열을 입력받고, int 타입을 리턴한다. 이를 간단하게 아래와 같이 표기할 수 있다.

  • arrSum : [int] -> int 

 

2. 문제를 쪼개고 경우의 수 나누기

 

주어진 문제를 쪼갤 기준을 정하고, 정한 기준에 따라 문제를 더 큰 경우와 작은 경우로 구분할 수 있는지 확인한다.

일반적인 경우 입력값으로  이 기준을 정하는데, 이때 중요한 관점은 입력값이나 문제의 순서와 크기다.

주어진 입력값 또는 문제 상황을 크기로 구분할 수 있거나, 순서를 명확하게 정할 수 있다면 문제를 구분하는 데 도움이 된다. 그리고 구분된 문제를 푸는 방식이 순서나 크기와 관계없이 모두 같다면, 문제를 제대로 구분한 것이다.

 

  • 함수 arrSum의 경우 입력값인 리스트(배열)의 크기에 따라, 더 작은 문제로 나눌 수 있다.
  • arrSum(new int[]{1, 2, 3, 4}) 를 구하는 방법과 arrSum(new int[]{2, 3, 4]} 을 구하는 방법은 동일하므로, 이 구분은 적절하다고 판단할 수 있다.

 

이제 문제에서 주어진 입력값에 따라, 경우의 수를 나눈다.

일반적으로 문제를 더 이상 쪼갤 수 없는 경우와 그렇지 않은 경우로 나눈니다.

 

  • 함수 arrSum은 입력값이 빈 배열인 경우와 그렇지 않은 경우로 나눌 수 있다. 각각의 경우는 다른 방식으로 처리해야 한다.
  • arrSum: [number] => arrSum(new int[]{}) / arrSum(new int[]{e1, e2, ..., en]}

 

3. 단순한 문제 해결하기

 

문제를 여러 경우로 구분한 다음, 가장 해결하기 쉬운 문제부터 해결한다. 이를 재귀의 기초(base case)라고 부른다.

재귀의 기초는 나중에 재귀 함수를 구현할 때, 재귀의 탈출 조건(재귀 호출이 멈추는 조건)을 구성한다.

  • 함수 arrSum을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열일 경우이고, 이때 arrSum(new int[]{}) 의 리턴값은 0이다.
  • arrSum: [number] => arrSum(new int[]{}) = 0 / arrSum(new int[]{e1, e2, ..., en]}

 

4. 복잡한 문제 해결하기

 

남아있는 복잡한 경우를 해결한다.

  • 길이가 1 이상인 배열이 함수 arrSum에 입력된 경우, 맨 앞의 요소에 대한 결과를 따로 구하고, 나머지 요소를 새로운 입력값으로 갖는 문제로 구분하고, 이를 해결하여 얻은 결과를 head에 더한다.
  • arrSum: [number] => numberarrSum(new int[]{}) = 0 / arrSum([e1, e2, ..., en]) = arrSum(new int[]{e1} + arrSum(new int[]{e2, ..., en]}
  • 배열을 head와 나머지 부분(tail)으로 구분하는 방법만 안다면, 함수 arrSum을 재귀적으로 구현할 수 있다.

 

5. 코드 구현

public int arrSum(int[] arr) {
  //Base Case : 문제를 더 이상 쪼갤 수 없는 경우 (재귀의 기초)
  if (arr.length==0) {
    return 0;
  }
  //Recursive Case : 그렇지 않은 경우
  //문제를 더 이상 쪼갤 수 없는 경우
  
  //head: 배열의 첫 요소
  int head = arr[0];
  //tail: 배열의 첫 요소만 제거된 배열
  int[] tail = Arrays.copyOfRange(arr,1,arr.length);
  
  return head + arrSum(tail);
}

 

 

 

 

728x90