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

이전글

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

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

 

순환적으로 사고하기(Recursive Thinking)

---

Recursion은 수학함수 계산에만 유용한가?

• 수학함수 뿐만 아니라 다른 많은 문제들을 recursion으로 해결할 수 있음

문자열의 길이 계산

• 문자열이 공백이라면 0 반환
• 아니라면 총 문자열의 길이는 첫번째 문자를 뺀, 전체 문자열 길이 + 1이다.

	// 문자열 s의 길이 게산
	public static int length(String s)
	{
		if(s.equals(""))
		{
			return 0;
		}
		return 1+ length(s.substring(1));
	}

	// 문자열 s의 길이 구함
	@Test
	void lengthTest() {
		System.out.println("lengthTest");
		System.out.println(Main.length("abcd"));
		System.out.println(Main.length(""));
	}

4
0

 

문자열의 프린트

• 문자열이 공백이라면 종료
• 아니라면 첫번째 문자를 출력하고 첫번째 문자를 제외한 문자열을 재귀적으로 호출

	// 문자열의 프린트
	public static void printChars(String s)
	{
		if(s.equals(""))
		{
			System.out.println();
			return;
		}
		else
		{
			System.out.print(s.charAt(0));
			printChars(s.substring(1));
		}
	}

	// 문자열 s를 앞에서부터 출력
	@Test
	void printCharsTest() {
		System.out.println("printChars Test");
		Main.printChars("abcd");
	}

abcd

 

문자열을 뒤집어 프린트

	// 문자열을 뒤집어서 프린트
	public static void printCharsReverse(String s)
	{
		if(s.equals(""))
		{
			return;
		}
		else
		{
			printCharsReverse(s.substring(1));
			System.out.print(s.charAt(0));
		}
	}

	// 문자열 s를 뒤집어 출력
	@Test
	void printCharsReverseTest() {
		System.out.println("printCharsReverse Test");
		Main.printCharsReverse("abcd");
		System.out.println();
	}

dcba

 

순차 탐색

• data[0]에서 data[n-1] 사이에서 target을 검색한다.
• target이 존재하면 배열 인덱스, 존재하지 않으면 -1을 반환한다.

	// 순차 탐색
	public static int search(int[] data, int n, int target)
	{
		if(n<=0)
		{
			return -1;
		}
		else if(target==data[n-1])
		{
			return n-1;
		}
		else
		{
			return search(data, n-1, target);
		}
	}

	// 순차탐색, 찾고자 하는 값의 위치를 반환, 없으면 -1 반환
	@Test
	void searchTest() {
		int[] data = {1,2,3,4,5};
		System.out.println("searchTest");
		System.out.println(Main.search(data, data.length, 3));
	}

2

 

최대값 찾기

• data[0]에서 data[n-1] 사이에서 최대값을 찾아 반환한다.

	// 최대값 찾기
	public static int findMax(int n, int[] data)
	{
		if(n==1)
		{
			return data[0];
		}
		// data[0]에서 data[n-1] 사이에서 최대값을 반환
		return Math.max(data[n-1], findMax(n-1, data));
	}

	// 최대값 찾기
	@Test
	void findMaxTest() {
		int[] data = {1,2,3,4,5};
		System.out.println("findMaxTest");
		System.out.println(Main.findMax(data.length, data));
	}

5

 

2진수로 변환하여 출력

• 음이 아닌 정수 n을 이진수로 변환하여 출력한다.
• n을 2로 나눈 몫을 먼저 2진수로 변환하여 출력한다.
• n을 2로 나눈 나머지를 출력한다.

	// 2진수로 변환하여 출력
	public static void printInBinary(int n)
	{
		if(n<2)
		{
			System.out.print(n);
		}
		else
		{
			printInBinary(n/2);
			System.out.print(n%2);
		}
	}

	// 2진수로 변환하여 출력
	@Test
	void printInBinaryTest() {
		System.out.println("printInBinaryTest");
		Main.printInBinary(8);
		System.out.println();
	}

1000

 

Disjoint Sets

• 배열 A의 A[0], ..., A[m-1]과 배열 B의 B[0], ... , B[n-1]에 정수들이 정렬되어 저장되어 있을 때 두 배열의 정수들이 disjoint(서로소)한지 검사한다.

	// Disjoint Sets
	// 배열 A의 A[0], ... , A[m-1]과 배열 B의 B[0], ... , B[n-1]
	// 에 정수들이 정렬되어 저장되어 있을 대 두 배열의 정수들이 disjoint한지 검사한다.
	// disjoint란 두 집합의 원소들이 같은 것이 없어야 함
	public static boolean isDisjoint(int m, int A[], int n, int B[])
	{
		if(m<0 || n<0)
		{
			return true;
		}
		else if(A[m]==B[n])
		{
			return false;
		}
		else if(A[m]>B[n])
		{
			return isDisjoint(m-1, A, n, B);
		}
		else
		{
			return isDisjoint(m, A, n-1, B);
		}
	}

	// Disjoint Sets
	@Test
	void isDisjointTest() {
		int[] A = {1,2,3,4,5};
		int[] B = {6,7,8,9,10};
		System.out.println("isDisjointTest");
		System.out.println(Main.isDisjoint(A.length-1, A, B.length-1, B));	
	}

true

 

Recursion VS Iteration

---

• 모든 순환함수는 반복문(iteration)으로 변경 가능함
• 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능함
• 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함
• 하지만 함수 호출에 따른 오버헤드가 있음 (매개변수 전달, 액티베이션 프레임 생성 등)

 

References

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