[JAVA] 재귀함수(Recursion)

재귀함수 (Recursion)

• 재귀의 사전적 의미 : 원래의 자리로 되돌아가거나 되돌아옴
• 자기 자신을 호출하는 함수
• 반복적인 작업을 간결하게 해결 할 수 있다.

구글의 재귀(Recursion) 검색시 이미지 - 이것을 찾으셨나요? - Recursion 클릭시 같은 화면 반복이 된다.

// 재귀함수 예제

class Recursion{
    void recursion(){
        System.out.println("제발 그만해..");
        recursion();
    }
}

// recursion() 호출시

/*
제발 그만해..
제발 그만해..
제발 그만해..
제발 그만해..
제발 그만해..
제발 그만해..
제발 그만해..
제발 그만해..
..
*/

재귀 함수의 장점

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

재귀 함수의 단점

• 반복문과 달리, 코드의 흐름 직관적 파악이 안된다. (선언형 프로그래밍)
• 반복하여 메서드를 호출하여 지역변수, 매개변수, 반환값을 process stack의 저장
  • 반복문보다 메모리를 더 많이 사용
• 메서드를 종료된 이후에 복귀를 위한 컨텍스트 스위칭* 비용 발생

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

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

재귀 함수의 템플릿

public type recursive(input1, input2, ...) {

  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  // 종료 조건
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  
  // recursive Case
  // 그렇지 않은 경우
  // 문제의 정의
  return 더 작은 문제로 새롭게 정의된 문제
  // 예1. someValue + recursive(input1Changed, input2Changed, ...)
  // 예2. someValue * recursive(input1Changed, input2Changed, ...)

}

예제1 1부터 num 까지의합

5  -> 1+2+3+4+5 = 15

public class Recursion { 
  public int sumTo(int num){
  
  // 종료조건, num이 0되면 종료
  if (num == 0) {
    return 0;
  }

  // 문제 정의
  return num + sumTo(num - 1);
  // num값에 num-1값을 재귀함수로 호출하여 더한다.
  
  }
}

• 5 + ( 4 + 3 + 2 + 1) -> 4 + (3 + 2 + 1) -> 3 + (2+1) -> 2 +(1) -> 1+(0) -> 종료 조건
• 리턴은 역순 (1) + 0 ->  (2)  + 1(1+0) -> (3) + 3(2+1) ->  (4) + 6(3+2+1) -> (5) + 10(4+3+2+1) -> 15 (5+4+3+2+1)  

 

예제2. 피보나치(fibonnacci) 수열

//  피보나치 수열의 num번째항 구하기

public class Recursion {  
	public int fibonacci(int num){
		//TODO..

    // 종료조건
    if(num == 0) return 0; // 피보나치의 수열 첫번째항
    if(num == 1) return 1; // 피보나치의 수열 두번째항
    // 두항은 항상 고정된다.

    // 문제의 정의
    return fibonacci(num-1) + fibonacci(num-2); // 피보나치 수열의 현재 값은 앞에 두항의 덧셈이다.
    // 1 = 1 + 0
    // 2 = 1 + 1
    // 3 = 2 + 1
    //  5 = 3 + 2
    // 8  = 5 + 3
	}
}

예제3. 배열의 순서를 뒤집어서 리턴

ex. { 1 ,2, 3, 4 } -> { 4, 3, 2, 1}

  public class Recursion { 
	public int[] reverseArr(int[] arr){
  
      // 종료 조건
      if(arr.length == 0) return arr; // 빈 배열인 경우 빈배열 그대로 리턴
        
      // 문제 정의
      int tail = arr[0]; // 맨앞 숫자가 맨뒤로 간다.
      int[] head = reverseArr(Arrays.copyOfRange(arr, 1, arr.length)); // 맨앞 숫자를 뺀 나머지를 재귀함수를 통해 구한다.

      int[] newArr = new int[arr.length]; // reverse한 것을 복사할 배열
      System.arraycopy(head, 0, newArr, 0, head.length); // 재귀 함수를 통해 구한 배열을 새배열에 앞부분부터 복사 
      newArr[arr.length-1] = tail; // 맨처음 뺀 첫번째 숫자를 맨뒤에 추가

      return newArr; // 배열 리턴
   }
}

• 배열의 맨앞을 빼두고 (tail), 나머지를 재귀함수로 호출하여 저장 (head)
• 새배열을 만들어 head를 앞에 복사, 맨뒤에 tail 추가 
  • { 1, 2, 3, 4}  -> 1 {2,3,4} -> 2 {3, 4} -> 3 {4} -> 4 {} - > 종료조건
  • 리턴이 역순으로된다.  {} 4 -> {4} 3 -> {4, 3}  2 -> {4, 3, 2}  1 -> {4, 3, 2, 1}

 

*컨텍스트 스위칭이란?

• 멀티프로세스 환경에서 실행중이던 프로세스를 중단하고 다른프로세스를 실행하는것
  • 실행중이던 프로세스의 정보값들을 저장해야함
  • 컨텍스트 스위칭이 자주 발생하면 오버헤드가 발생할수있다.