[Java] 재귀 함수

📌재귀함수

재귀란 원래의 자리로 되돌아가거나 되돌아오는 것이다.

재귀 함수의 장점

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

재귀 함수의 단점

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

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

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

코드 구현하는 법

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

📌재귀함수 예제

구구단

// 반복문으로 구현한 구구단 메서드
public void Gugudan(int level) {
  for(int count = 1; count < 10; 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);
}

팩토리얼

// 반복문으로 구현한 팩토리얼 메서드
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);
}