Algorithm - Recursion의 개념과 기본 예제들

1. Basic structure of recursion

recursion의 기본적인 구조는 Base area, Recursion area로 나뉘며, 각각의 area는 다음과 같은 특성을 갖는다.

• Base area : Recursion 내에 적어도 하나의 base area가 존재해야 하며, 이 영역은 infinite loop를 순회하는 recursion을 종료시키는 역활을 한다.
• Recursion area : 모든 Case는 base case에 수렴하도록 설계해야 한다.

 

이번에는 Recursion을 더 잘 이해하고, 일반적인 반복문과의 차이점을 확인하기 위해서 1) 일반적인 반복문으로 구현 했을 때와 2) Recursion으로 구현했을 때을 비교해보도록 하겠다.

 

2. Sequential search

2.1. General infinite loop

public class Test {
	public static void main(String[] args) {
		int[] list = {1, 2, 3, 4, 5};
		
		int index = getIndex(list, list.length, 2);
		System.out.printf("2's index is %d.\n", index);
	}
	
	private static int getIndex(int[] list, int size, int target) {
		for(int i=0; i<size; i++) {
			if(list[i] == target)
				return i;
		}
		return -1;
	}
}

• 배열내에서 target 변수를 찾기 위해서 list [0] ~ list [size-1]을 순회하며 찾는다. 
• 이때, 종점인 size-1은 getIndex 메서드가 parameter로 size를 받았기 때문에 explicit parameter로 표현되어 있지만,  시작점인 0는 parameter로 받지도 않았으며, 어디에도 sequential search를 부터 시작한다고 명시하지 않았기 때문에 0은 implicit parameter로 표현한 것이다. 
• 즉, 코드 상에 명시가 되어 있으면 explicit parameter, 명시되어 있지 않으면 implicit parameter  ★
• Generic infinite loop에서는 가독성을 위해서 생략할 수 있는 것은 생략하는 것이 좋다.

 

2.2. Recursion

public class Test {
	public static void main(String[] args) {
		int[] list = {1, 2, 3, 4, 5};
		
		int index = findIndex(list, 0, list.length-1, 5);
		System.out.printf("2's index is %d.\n", index);
	}
	
	private static int findIndex(int[] list, int begin, int end, int target) {
		if(begin>end)
			return -1;
		else if(list[begin] == target)
			return begin;
		else
			return findIndex(list, begin+1, end, target);
	}
}

import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] list = {1, 2, 3, 4, 5};
		
		System.out.print("Enter: ");
		int target = scan.nextInt();
		
		int index = getIndex(list, list.length-1, target);
		System.out.printf("%d's index is %d.\n", target, index);
	}
	
	private static int getIndex(int[] list, int end, int target) {
		if(0>end) 
			return -1;
		else if(list[end] == target)
			return end;
		else
			return getIndex(list, end-1, target);
	}
}

• 시작점과 종점 사이에 찾고자 하는 값이 존재하는지 여부를 확인
• 시작점 begin과 종점 end를 parameter로 받았기 때문에 두 개의 변수는 모두 explicit parameter라 할 수 있다.
• Recursion는 암시적인 매개변수(Implicit parameter)보다 명확한 매개변수(explicit parameter)를 사용해야 한다.
  ▶ 일반적인 반복문은 메서드를 호출할 경우만 생각하면 되지만, Recursion은 메소드를 호출할 경우 뿐만 아니라 
       본인 스스로를 호출할 경우까지 생각해야 하기 때문에 Recursion에서는 일반적으로 explicit parameter를 사용
• 하지만, Recursion을 다 작성하고, 필요에 따라 일부 매개변수를 제거할 수 있다.

 

2.3. Recursion의 다른 버전

import java.util.Scanner;

public class Test {	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] list = {1, 2, 3, 4, 5};
		
		System.out.print("Enter: ");
		int target = scan.nextInt();
		
		int index = getIndex(list, 0, list.length-1, target);
		System.out.printf("%d's index is %d.\n", target, index);
	}
	
	private static int getIndex(int[] list, int begin, int end, int target) {
		// ** Base case
		if(begin>end)
			return -1;
		
		// ** Recursion case
		// * 첫 번째 경우) index = mid인 경우
		int mid =  (begin+end)/2;	
		if(list[mid]==target)
			return mid;
		// * 두 번째 경우) 0 <= index < mid
		int index = getIndex(list, begin, mid-1, target);
		if(index!=-1)
			return index;
		else
			// * 세 번째 경우) mid < index <= end
			return getIndex(list, mid+1, end, target);
		
	}
}

• 이 Recursion은 세 영역으로 나누어 확인한다. 첫 번째) middle, 두 번째) [0, middle), 세 번째) (middle, end]
• Q) 왜 두 번째 영역에서 끝점(mid)부터 하나씩 줄이면서 오는가? 시작점(0)부터 하나씩 늘리면서 오면 안되는가?★
  ▶ 만약 시작점부터 +1씩 늘리면서 오면 첫 번째 인덱스( list[0] )를 확인하지 않고, 바로 두 번째 인덱스( list[1] )부터 확인하기 때문에 문제가 발생한다. 따라서 이미 확인한 중간 지점(mid) 직전 인덱스를 시작으로 -1씩 줄여가며 확인한다.
• Tip ) Recursion contents를 작성하기 전에 Base case와 Recursion case을 먼저 나누어서 "언제 infinite loop를 벗어나야 하는가?" 등을 생각하면서 base case를 먼저 작성하는 것이 좋다.

 

3. Find the maximum by using recursion

import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.print("Enter size of list: ");
		int size = scan.nextInt();
		int[] list = new int[size];
		
		for(int i=0; i<size; i++)
			list[i] = scan.nextInt();
		
		int max = getMaximum(list, 0, 0);
		System.out.printf("Maximum number is %d.\n", max);
	}
	
	private static int getMaximum(int[] list, int begin, int max) {
		if(begin>list.length-1)
			return max;
		else {
			if(list[begin]>=max)
				max = list[begin];
			
			return getMaximum(list, begin+1, max);
		}
	}
}

import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		System.out.print("Enter size of list: ");
		int size = scan.nextInt();
		int[] list = new int[size];
		
		for(int i=0; i<size; i++)
			list[i] = scan.nextInt();
		
		int max = getMaximum(list, 0, list.length-1);
		System.out.printf("Maximum number is %d.\n", max);
	}
	
	private static int getMaximum(int[] list, int begin, int end) {
		if(begin==end)
			return list[begin];
		else 
			return Math.max(list[begin], getMaximum(list, begin+1, end));
		
	}
}

• getMaximum 메서드: 뒤에서부터 차례대로 begin 인덱스와 나머지 영역(=begin 이후)의 최대 값을 비교하는 메서드
• ★ 아이디어) begin 인덱스가 end 인덱스와 동일할 때까지 recursion한 뒤, 차례차례 뒤에서부터 비교한다.

import java.util.Scanner;

public class Test {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int size = 0;
		
		while(true) {
			System.out.print("Size: ");
			size = scan.nextInt();
			
			if(size<=0)
				System.out.println("Size of list is less than zero.");
			else
				break;
		}	
		
		int[] list = new int[size];
		for(int i=0; i<size; i++)
			list[i] = scan.nextInt();
		
		int maximum = getMaximum(list, 0, list.length-1);
		System.out.printf("Maximum value is %d.\n", maximum);
	}
	
	private static int getMaximum(int[] list, int begin, int end) {
		if(begin==end)
			return list[begin];
		else {
			int mid = (begin+end)/2;
			int max1 = Math.max(list[begin], getMaximum(list, begin, mid));
			int max2 = Math.max(list[mid+1], getMaximum(list, mid+1, end));
			return Math.max(max1, max2);
		}	
	}
}

• 위 Recursion은 [begin, middle]과 (middle+1, end], 두 개의 영역으로 나누어 생각한다.
• max1 은 [begin, middle]에서의 최대값, max2 은 (middle+1, end]에서의 최대값을 의미

 

4. Binary search

private static int getIndex(String[] list, String target) {
		int begin = 0;
		int end = list.length - 1;
		
		while(begin<=end) {
			int mid = (begin+end) / 2;
			
			if(list[mid].equalsIgnoreCase(target))
				return mid;
			else if(list[mid].compareToIgnoreCase(target)>0)
				end = mid-1;
			else
				begin = mid+1;
		}
		
		return -1;
	}

private static int getIndex(String[] list, int begin, int end, String target) {
		if(begin>end)
			return -1;
		else {
			int mid = (begin+end) / 2;
			if(list[mid].equalsIgnoreCase(target))
				return mid;
			else if(list[mid].compareToIgnoreCase(target)>0)
				return getIndex(list, begin, mid-1, target);
			else
				return getIndex(list, mid+1, end, target);
		}
	}

 

5. Recursion 원칙

• 반드시 하나 이상의 base case가 존재해야 한다.
• Recursion case는 반드시 base case로 수렴해야 한다.
  (그래야 Infinite loop에서 빠져 나올 수 있다.)
• implicit parameter보다 explicit parameter를 사용하는 것이 좋다.