재귀 함수 알고리즘 예 하향식,상향식 분석하기

재귀 알고리즘은 복잡해서 이해하기 어렵습니다.

하향식, 상향식 분석을 이용하면 보다 쉽게 이해할 수 있습니다.

하향식 분석은 맨 위의 재귀에서 시작해 아래 단계로 가면서 하나하나 조사하는 것이고

상향식 분석은 가장 아랫단의 재귀부터 시작해 가장 위의 재귀까지 조사하는 것입니다.

예를 통해 살펴보록 하겠습니다.

static void abc(int n) {
	if(n>1) {
		abc(n-1);
		abc(n-2);
	}
	System.out.println(n);
}
public static void main(String[] args) {
	abc(4);
}

결과 : 1 0 2 1 3 1 0 2 4

코드는 간단하지만 결과는 복잡합니다.

1. 하향식 분석

-n에 4가 들어가면 abc(3) 재귀가 시작됩니다.

abc(3)이 모두 끝나고 나면 abc(2)가 시작됩니다.

 

-abc(3)은 다시 abc(2)와 abc(1)로 갈라지고

abc(2)가 모두 완료되어야 abc(1)이 시작됩니다.

 

-abc(2)는 또다시 abc(1)과 abc(0)으로 갈라집니다.

abc(1)은 n>1을 충족하지 못하기 때문에 1을 출력합니다.

abc(0)도 마찬가지이므로 0을 출력합니다.

이제 abc(2)의 출력 부분이 실행돼 2가 출력되고

abc(1)이 실행돼 1이 출력됩니다.

 

-abc(3)에서 파생된 abc(2)와 abc(1)가 실행되고 나면

abc(3)의 출력부분이 실행돼 3이 출력됩니다.

...

이런식으로 위에서부터 타고 내려오면서 분석하는 것이 하향식 분석입니다.

 

2. 상향식 분석

가장 아랫단은 abc(1)과 abc(0)입니다.

이들은 각각 1과 0을 출력하고

이들의 윗 단계인 abc(2)는 이제 2를 출력합니다.

abc(2)가 모두 완료되면 

abc(1)이 실행돼 1이 출력되면

abc(3)이 실행돼 3이 출력됩니다.

......