[Java Algorithm] 재귀(Recursion)

재귀 (Recursion) 함수란?

• 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수
• 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결함으로써 원래 문제를 해결해 나가는 방식
• 일반 반복문 <-> 재귀 함수 쌍방으로 구현 가능함

 

장점

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

단점

• 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어렵다.
• 반복하여 매서드를 호출하며 지역변수, 매개변수, 반환값을 모두 process stack에 저장하게 되어 반복문에 비해 메모리 사용이 많아진다.

사용 조건

• 문제의 크기를 점점 작은 단위로 쪼갤수 있어야 한다.
• 재귀 호출이 종료되는 시점(base case)이 존재해야 한다.
• 모든 입력은 base case로 수렴해야 한다.

사용 상황

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

 

예시) 자연수로 이루어진 리스트(배열)를 입력받고, 리스트의 합을 리턴하는 메서드 `arrSum` 을 작성하세요.

//일반 for문 사용
public int arrSum(int[] arr) {
  int sum = 0;
  for(int i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

// 1. 문제를 작게 쪼개기

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([])

// 2. 문제 해결하기

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;

// 재귀함수 사용
public int arrSum (int[] arr) {
  // 빈 배열을 받았을 때 0을 리턴하는 조건문
  //   --> 가장 작은 문제를 해결하는 코드 & 재귀를 멈추는 코드
  if (arr.length == 0) {
    return 0;
  }
  // 배열의 첫 요소 + 나머지 요소가 담긴 배열을 받는 arrSum 함수
  //   --> 재귀(자기 자신을 호출)를 통해 문제를 작게 쪼개나가는 코드
	return arr[0] + arrSum(arr);
}

 

재귀를 활용할 상황을 판별하는 방법 (위 예제를 예시로)

 

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

• 문제를 가장 추상적, 단순하게 정의한다.
• arrsum: [int] -> int 이며 해설하면 int 타입을 요소로 갖는 배열을 입력으로 받고, int 타입을 리턴한다.

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

• 중요한 관점은 입력값이나 문제의 순서와 크기이다.
• arrSum(new int[]{1, 2, 3, 4}) 를 구하는 방법과 arrSum(new int[]{2, 3, 4]} 을 구하는 방법은 동일하다.

3. 단순한 문제 해결하기

• 가장 해결하기 쉬운 문제부터 해결한다.
• 이를 재귀의 기초(base case)라고 부르고, 재귀의 탈출 조건을 구성한다.
• arrsum을 더 이상 쪼갤 수 없는 경우는 입력값이 빈 배열인 경우이다. 이때 arrSum(new int[]{}) 의 리턴값은 0

4. 복잡한 문제 해결하기

• 배열 맨 앞의 요소(head)에 대한 결과를 따로 구하고, 나머지 요소(tail)를 새로운 입력값을 갖는 문제로 구분하고 이를 해결하여 얻은 결과를 head에 더한다.

 

예제

1. sumTo

수(num)를 입력받아 1부터 num까지의 합을 리턴

public class Solution { 
  public int sumTo(int num){

    if (num <= 0) {
      return 0;
    }
    else{
      return num + sumTo(num - 1);
    }
  }
}

 

2. isOdd

수를 입력받아 홀수인지 여부를 리턴

public class Solution { 
	public boolean isOdd(int num) {

    if (num == 0) return false; // 2를 num만큼 뺀 후 남은 수가 0이므로 짝수
    if (num == 1) return true;  // 2를 num만큼 뺀 후 남은 수가 1이므로 홀수

    if (num < 0) return isOdd(-num); // 음수를 입력받은 경우 -1을 곱해줌

    return isOdd(num - 2);
      // isOdd(5 - 2)
        // isOdd(3 - 2)
          // isOdd(1) -> base case로 return true;
  }
}

 

3. factorial

수를 입력받아 n-factorial(n!; 엔-팩토리얼) 값을 리턴

public class Solution { 
	public int factorial(int num){

    if (num == 0) {
      return 1;
    }
    return num * factorial(num - 1);
      // 4 * factorial(4 - 1)
        // 3 * factorial(3 - 1)
          // 2 * factorial(2 - 1)
            // 1 * factorial(1 - 1) 
          // 1 * factorial(0)         -> base case 이므로 return 1;
        // 2 * factorial(1 * 1)
      // 3 * factorial(2 * 1)
    // 4 * factorial(3 * 2)
    
    // factorial(4) = 24
  } 
}

 

4. fibonacci

수(num)를 입력받아 피보나치 수열의 num번째 요소를 리턴

public class Solution {  
	public int fibonacci(int num){

    if (num <= 1){
    return num;
    }
    return fibonacci(num - 1) + fibonacci (num - 2);
	}
}

 

 

 

5. arrSum

배열을 입력받아 모든 요소의 합을 리턴

public class Solution { 
	public int arrSum(int[] arr){

    if(arr.length == 0) return 0;

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

    return head + arrSum(tail);
    // input [1, 2, 3, 4]
      // head[1] + [2, 3, 4]
        // head[1+2] + [3, 4]
          // head[1+2+3] + [4]
            // head[1+2+3+4] + [ ] -> return = 0;
  }
}

 

7. drop

수(num)와 배열을 입력받아 차례대로 num개의 요소가 제거된 새로운 배열을 리턴

public class Solution { 
	public int[] drop(int num, int[] arr){
if (arr.length == 0) { // 배열에 더 이상 제거할게 없을 경우 그대로 리턴
  return arr;
}
if (num == 0) { // 0개를 제거해야 하는 경우
  return arr;
}
// 작은 단위로 쪼갤 수 있는 경우
int head = num - 1;
int[] tail = Arrays.copyOfRange(arr, 1, arr.length);

return drop(head, tail);
  // input(2, [1, -2, 1, 3])
   // head(num - 1), tail[]
    // (2 - 1), [-2, 1, 3]
      // (1 - 1), [1, 3]
        // (0), [1, 3] -> return arr;
	} 
}

 

8. take

수(num)와 배열을 입력받아 차례대로 num개의 요소만 포함된 새로운 배열을 리턴

public class Solution { 
	public int[] take(int num, int[] arr){
    if(arr.length == 0 || num == 0) { //입력된 배열이 빈 배열인 경우, 입력된 num이 0인 경우
      return new int[]{}; //빈 배열을 반환합니다.
    }
    //배열의 가장 첫번째 요소만을 가지고 있는 head 배열을 선언, 할당합니다.
    int[] head = Arrays.copyOfRange(arr, 0, 1);

    //남은 요소를 가지고 있는 tail 배열을 선언, 할당하고, 해당 배열의 요소가 모두 제거될 때까지 재귀함수를 호출합니다.
    //한번 호출될 때마다, num을 하나씩 줄여줍니다. head 배열에 현재 선택된 요소가 있기 때문에, 앞으로 선택할 요소를 나타내는 num을 1씩 줄여서 재귀함수가 실행되어야 합니다.
    int[] tail = take(num - 1, Arrays.copyOfRange(arr, 1, arr.length));

    //재귀함수가 모두 호출된 이후에, 할당된 head배열과 tail 배열을 합친 새로운 배열을 선언, 할당합니다.
    //새로운 배열을 선언합니다. 배열의 크기는 head.length와 tail.length를 합친 크기로 선언합니다.
    int[] dest = new int[head.length + tail.length];
    
    //System.arraycopy메서드를 사용하여, head, tail 두 배열의 요소를 모두 dest 배열에 복사합니다.
    //System.arraycopy(src, srcPos, dest, destPos, length);
    System.arraycopy(head, 0, dest, 0, head.length);
    System.arraycopy(tail, 0, dest, head.length, tail.length);

    return dest;
    //input 2, [1, 2, 3, 4]
    // [head], (num - 1) [tail]
      // [1], (2 - 1) [2, 3, 4]
        // [1, 2], (1 - 1) [3, 4] -> num = 0, return new int[]{};
	} 
}

 

10. and

배열을 입력받아 모든 요소의 논리곱(and)을 리턴해야 합니다.

public class Solution {  
	public boolean and(boolean[] arr){

    if (arr.length == 0){
      return true;
    }
    boolean head = arr[0];
    boolean[] tail = Arrays.copyOfRange(arr, 1, arr.length);

    return (head && and(tail));
	} 
}

 

12. reverseArr

배열을 입력받아 순서가 뒤집힌 배열을 리턴해야 합니다.

public class Solution { 
	public int[] reverseArr(int[] arr){
      if(arr.length == 0) {
        return new int[]{};
      }
      //배열의 가장 마지막 요소만을 가지고 있는 head 배열을 선언, 할당합니다.
      int[] head = Arrays.copyOfRange(arr, arr.length - 1, arr.length);

      //남은 요소를 가지고 있는 tail 배열을 선언, 할당하고, 해당 배열의 요소가 모두 제거될 때까지 재귀함수를 호출합니다.
      int[] tail = reverseArr(Arrays.copyOfRange(arr, 0, arr.length - 1));

      //재귀함수가 모두 호출된 이후에, 할당된 head배열과 tail 배열을 합친 새로운 배열을 선언, 할당합니다.
      //새로운 배열을 선언합니다. 배열의 크기는 head.length와 tail.length를 합친 크기로 선언합니다.
      int[] dest = new int[head.length + tail.length];
      
      //System.arraycopy메서드를 사용하여, head, tail 두 배열의 요소를 모두 dest 배열에 복사합니다.
      System.arraycopy(head, 0, dest, 0, head.length);
      System.arraycopy(tail, 0, dest, head.length, tail.length);

      return dest;
	} 
}