알고리즘 #10 (재귀 알고리즘) [JAVA]

알고리즘 10일차

 

요즘 시험이랑 과제에 허덕이느라 알고리즘에 소홀했다. 열심히 해야돼...

 

[2021.10.6]

백준 동적 계획법(DP) 문제를 푸는 것이 다음 순서였는데, DP를 잘몰라서 재귀 알고리즘부터 공부했다.

책 '자료구조와 함께 배우는 알고리즘 입문 자바편'을 이용했다.

 

재귀 함수란?

어떤 함수에서 자신을 다시 호출하여 작업을 수행하는 방식의 함수

 

재귀함수를 이용해서 덧셈을 하는 프로그램을 짜봤다.

import java.util.*;

public class recursive {

	static int addition(int sum, String nums[]) {
		
		if(nums.length == 0)
			return sum;
		else {
			int n = Integer.parseInt(nums[0]);
			
			String newNums[] = new String[nums.length - 1];
			for(int i=1; i<nums.length; i++) {
				newNums[i-1] = nums[i];
			}
			return addition(sum + n, newNums);
		}  
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.print("덧셈을 할 숫자를 입력해주세요 (각 수는 공백으로 구별) : ");
		String nums[] = sc.nextLine().split(" ");
				
		int sum = 0;
		System.out.println(addition(sum, nums));	
	}
}

결과는 이런식으로 출력된다.

 

이제 대충 재귀함수를 사용해봤으니 책의 예제를 따라해봤다.

import java.util.*;

public class recursive {
	
	static void recur(int n) {
		if (n>0) {
			recur(n-1);
			System.out.print(n + " ");
			recur(n-2);
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		System.out.print("정수를 입력하세요 : ");
		int x = sc.nextInt();
		
		recur(x);
	}
}

이 프로그램에 정수 4를 넣으면 결과는 다음과 같다.

왜 이런 결과가 나오는지 한번에 이해하기 어려웠다.

이 recur 메서드를 분석하는 방법 중에는 하향식, 상향식 분석이 있다.

 

1. 하향식 분석

먼저, n이 4일 때 recur 메서드는

1) recur(4)

2) 4 출력

3) recur(3)

를 차례로 실행한다.

1), 3)번은 재귀함수 recur 메서드가 다시 실행되는데, 이러한 결과들을 그림으로 나타낸 모습은 다음과 같다.

recur에서 n이 0보다 작으면 아무 일도 일어나지 않으므로 생략하고, 중위순회방식으로 읽으면 1 2 3 2 4 1 2 가 결과가 된다.

*중위순회 : 왼쪽 자식 노드 - 부모노드 - 오른쪽 자식 노드 순으로 순회

 

2. 상향식 분석

recur(1) : recur(0) 1 recur(-1) → 1

recur(2) : recur(1) 2 recur(0) → 1 2

recur(3) : recur(2) 3 recur(1) → 1 2 3 1

recur(4) : recur(3) 4 recur(2) → 1 2 3 1 4 1 2

 

이 메서드는 하향식 분석의 경우 같은 메서드의 호출이 여러 번 나올 수 있기 때문에 지금의 경우에는 효율적이지 않음

 

상향식 분석으로 x에 7을 넣을 경우 결과를 예측해봤다.

recur(1) : recur(0) 1 recur(-1) → 1

recur(2) : recur(1) 2 recur(0) → 1 2

recur(3) : recur(2) 3 recur(1) → 1 2 3 1

recur(4) : recur(3) 4 recur(2) → 1 2 3 1 4 1 2

recur(5) : recur(4) 5 recur(3) → 1 2 3 1 4 1 2 5 1 2 3 1

recur(6) : recur(5) 6 recur(4) → 1 2 3 1 4 1 2 5 1 2 3 1 6 1 2 3 1 4 1 2

recur(7) : recur(6) 7 recur(5) → 1 2 3 1 4 1 2 5 1 2 3 1 6 1 2 3 1 4 1 2 7 1 2 3 1 4 1 2 5 1 2 3 1