재귀 알고리즘

재귀란?

: 어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적이라고 한다.

 

예시) 팩토리얼 구하기

package chap05;
import java.util.Scanner;
// 팩토리얼을 재귀적으로 구현

class Factorial {
	// 양의 정수 n의 팩토리얼을 반환합니다.
	static int factorial(int n) {
		if (n > 0)
			return n * factorial(n - 1);
		else
			return 1;
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("정수를 입력하세요.：");
		int x = stdIn.nextInt();

		System.out.println(x + "의 팩토리얼은 " + factorial(x) + "입니다.");
	}
}

factorial(3)을 호출하였을 때

 

하향식 분석과 상향식 분석

 

아래 예제 코드로 설명해보자.

package chap05;
import java.util.Scanner;
// 재귀 함수 이해하기

class Recur {
	// 재귀 함수
	static void recur(int n) {
		if (n > 0) {
			recur(n - 1);
			System.out.println(n);
			recur(n - 2);
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.print("정수를 입력하세요.：");
		int x = stdIn.nextInt();

		recur(x);
	}
}

실행 결과 :

정수를 입력하세요 : 4
1
2
3
1
4
1
2

 

하향식 분석 (top down)

매개변수 4를 전달했을 때 하향식 분석의 결과 (가장 위의 화살표부터 따라감)

: 가장 위쪽에 위치한 상자의 메소드 호출부터 시작해 계단식으로 자세히 조사하는 분석 기법

하지만, 위 그림에는 recur(1), recur(2)과 같이 같은 메소드의 호출이 여러번 있다.

따라서, 꼭대기(top)부터 분석하면 이렇게 같은 메소드의 호출이 여러 번 나올 수 있기 때문에

'하향식 분석이 반드시 효율적이다'라고 말할 수 없다.

 

 

상향식 분석 (bottom up)

: 아래쪽부터 쌓아 올리며 분석하는 방법

 

recur 메소드는 n이 양수일 때만 실행하므로 recur(1)부터 생각해보자.

 

출처 : Do it! 자료구조와 함께 배우는 알고리즘 입문 - 자바 편