[Java] 재귀 함수 (Recursion Function) 정리

재귀 함수(Recursion)란?

특정 함수 내에서 자기 자신을 호출하는 함수이다. 재귀 함수를 잘 활용하면 반복적인 작업을 해야 하는 문제를 좀 더 간결하게 풀어낼 수 있다.

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

 

재귀 함수 사용 조건

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

 

재귀 함수의 장점

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

 

재귀 함수의 단점

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

 

재귀 함수 예제

일반적인 재귀 함수의 템플릿

public type recursive(input1, input2, ...) {
  // Base Case : 문제를 더 이상 쪼갤 수 없는 경우
  if (문제를 더 이상 쪼갤 수 없을 경우) {
    return 단순한 문제의 해답;
  }
  // recursive Case
  // 그렇지 않은 경우
  return 더 작은 문제로 새롭게 정의된 문제
}

 

구구단 만들기

// 반복문으로 구현한 구구단 메서드
public void Gugudan(int level) {
  for(int count = 0; count < 9; count++) {
    System.out.printf("%d x %d = %d\n", level, count, level * count);
  }
}

// 재귀 호출로 구현한 구구단 메서드
public void Gugudan(int level, int count) {
  if(count > 9) {
    return;
  }
  System.out.printf("%d x %d = %d\n", level, count, level*count);
  Gugudan(level, ++count);
}

 

팩토리얼 (factorial) 만들기

// 반복문으로 구현한 팩토리얼 메서드
public int Factorial(int number) {
  int result = 1;
  for(int count = number; count > 0; count--) {
    result = result * count;
  }
  return result;
}

// 재귀 호출로 구현한 팩토리얼 메서드
public int Factorial(int number) {
  if(number <= 1) {
    return 1;
  }
  return number * Factorial(number - 1);
}