[Java] 재귀

재귀의 개념

자기 자신을 끝없이 호출하면서 같은 코드가 계속해서 실행되는 것.

장점

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

단점

• 반복문과 달리, 코드의 흐름을 직관적으로 파악하기 어려움.
• 많은 메모리를 사용하게 됨.
• 메서드가 종료된 이후에 복귀를 위한 컨텍스트 스위칭 비용이 발생함.

사용 조건

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

재귀 함수 사용 예시

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

1 + N번 까지의 합계 출력

public class PlusFunction2 {
	public static void main(String[] args)  {
		int N = 5;
		System.out.print("1부터 " + N + "까지의 합계 : " + PlusPlus(5));
	}
	
	// PlusPlus 출력 메서드 선언
	public static int PlusPlus(int n)
	{
		// n이 0인 경우 return
		if(n == 0)
			return 0;
				
		return n += PlusPlus(n-1); // 재귀함수 시작
	}
}

Return에서 N += 재귀함수를 호출하여 1부터 N까지의 합계를 구해준다.

피보나치 수열 구하기

public class FibonacciFunction {
	public static void main(String[] args)  {
		int n = 10;
		
		for(int i = 0; i < n; i++) // 피보나치 수열 출력
			System.out.print(Fibonacci(i) + " ");
	}
	
	// 피보나치 수열의 결과를 구하는 메서드 선언
	public static int Fibonacci(int n)
	{
		if(n == 0)
			return 0;
		
		if(n == 1 || n == 2)
			return 1;
		
		else 
			return Fibonacci(n - 1) + Fibonacci(n - 2);
	}
}

피보나치 수열은 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987…

이런식으로 n = (n-1) + (n+2) 이 계속해서 나오도록 하는 수열이다.