[알고리즘][Recursion] 재귀(Recursion) 기본 개념과 예제 3

이전글

https://yonghwankim-dev.tistory.com/194

[알고리즘] 재귀(Recursion) 기본 개념과 예제 2

 

순환적 알고리즘 설계

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 존재해야 함
• 모든 case는 결국 base case로 수렴해야 함
• 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 변경하라

 

순차 탐색 : 암시적 매개변수

아래의 예제는 배열의 맨 뒤쪽부터 0번째까지 target이 있는지 순차적으로 탐색하는 순차 탐색이다.

그런데 매개변수를 보면 배열의 크기만을 나타내는 n만이 존재한다. 이는 암시적으로 순차 탐색을 수행할 때 n-1번째부터 0번째까지 탐색하는 것을 나타낸다. 즉, 0은 암시적 매개변수이다.

	// 순차탐색, Recursion 버전
	// 이 메서드는 n-1번째부터 0번째까지 순차적으로 target과 같은 값이 있는지 탐색한다.
	// 탐색이 성공하면 위치를 반환한다.
	// 여기서 암시적으로 종료점을 0으로 설정하는 것을 볼 수 있습니다.
	public static int search(int data[], int n, int target)
	{
		if(n<0)
		{
			return -1;
		}	
		else if(data[n-1]==target)
		{
			return n-1;
		}
		else
		{
			return search(data,n-1,target);
		}
	}

	// 순차탐색, 암묵적으로 종료점을 0으로 설정
	@Test
	void searchImplicitTest()
	{
		int[] data = {1,2,3,4,5};
		System.out.println("searchImplicit Test");
		System.out.println(Main.search(data, data.length, 1));	
	}

0

 

순차 탐색 : 매개변수의 명시화

아래의 예제는 순차 탐색 메서드에서 매개변수에 시작점(begin)과 종료점(end)을 명시적으로 설정하여 탐색의 범위를 나타내고 재귀적으로 구현할 수 있습니다.

	// 순차탐색, Recursion 버전
	// 시작점(begin)과 종료점(end)을 설정하여 시작점과 종료점을 명시적으로 설정합니다.
	public static int search(int data[], int begin, int end, int target)
	{
		if(begin>end)
		{
			return -1;
		}
		else if(data[begin]==target)
		{
			return begin;
		}
		else
		{
			return search(data, begin+1, end, target);
		}
	}

	// 순차탐색, 명시적으로 시작점과 종료점을 설정
	@Test
	void searchExplicitTest()
	{
		int[] data = {1,2,3,4,5};
		System.out.println("searchExplicitTest Test");
		System.out.println(Main.search(data, 0, data.length, 5));
	}

4

 

이진탐색 : Recursion

• data[begin]에서 data[end] 사이에서 target을 검색한다.
• 매개변수에 begin과 end 변수를 명시적으로 설정하여 탐색의 시작점과 종료점을 설정한다.

	// 이진탐색, recursion 버전
	// 명시적으로 시작(begin)과 끝(end)을 재귀적으로 호출합니다.
	public static int binarySearch(int[] data, int target, int begin, int end)
	{
		if(begin>end)
		{
			return -1;	// 탐색 실패
		}
		else
		{
			int middle = (begin+end)/2;
			if(data[middle]==target)
			{
				return middle;
			}
			else if(data[middle]>target)
			{
				return binarySearch(data, target, begin, middle-1);
			}
			else
			{
				return binarySearch(data, target, middle+1, end); 
			}
		}		
	}

	// 이진탐색, Recursion
	// binarySearch 매개변수에 시작점과 종료점을 명시적으로 설정함
	@Test
	void binarySearchRecursionTest()
	{
		int[] data = {1,2,3,4,5};
		System.out.println("binarySearch Recursion Test");
		System.out.println(Main.binarySearch(data, 5, 0, data.length-1));
	}

4

 

2-SUM

• data[begin]에서 data[end] 사이에서 합이 k가 되는 상이 존재하는지 검사한다.
• 데이터는 오름차순으로 정렬되어 있다고 가정한다.
• base case에서 만약 중복 선택이 가능하다면 "=" 연산자를 빼면 된다.
• 매개변수에 시작점(begin)과 종료점(end)을 명시적으로 설정한다.

	public static boolean twoSum(int[] data, int begin, int end, int k)
	{
		// 만약 중복 선택이 가능하다면 "="을 빼면 됨
		if(begin>=end)
		{
			return false;
		}
		else 
		{
			if(data[begin]+data[end]==k)
			{
				return true;
			}
			else if(data[begin]+data[end]<k)
			{
				return twoSum(data, begin+1, end, k);
			}
			else
			{
				return twoSum(data, begin, end-1, k);	
			}
		}	
	}

	@Test
	void twoSumTest()
	{
		int[] data = {1,2,3,4,5};
		System.out.println("twoSum Test");
		System.out.println(Main.twoSum(data, 0, data.length-1, 3));
	}

true

 

재귀(Recursion) 알고리즘 정리

---

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
• 모든 recursion case는 결국 base case로 수렴해야 함
• 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 변경하는 것을 권고함

 

References

source code : https://github.com/yonghwankim-dev/inflearn_algorithm
[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌