반복과 재귀(Iteration, Recursion)

반복문과 재귀의 공통점

반복은 (for / while) 문을 통하여 작업이 완료될 때까지 계속 반복합니다.

 

재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법입니다.

 

반복문과 재귀를 통하여 유사한 작업을 수행할 수 있습니다.

 

반복문은 어떤 기준으로 반복할 것인가를 찾아내는 것이 중요하고, 이는 재귀 함수의 구현부를 의미합니다.

 

재귀 함수는 구현부를 통해 자기 자신을 호출하고 반복하게 됩니다.

 

반복문은 조건을 통해 반복문을 탈출하고, 재귀 함수도 특정 조건 시에 return을 통해 반복을 탈출합니다.

 

재귀 함수란?

- 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수

- 기본 부분(basis part)과 유도 파트(inductive part)로 구성된다. (기본 부분 = 조건 시에 return, 유도 파트 = 자기 자신 호출)

- 반복 구조에 비해 간결하고 이해하기 쉽다.

- 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다.

- 재귀 호출을 통해 반복적으로 스택이 쌓이기 때문에 메모리 및 속도에서 성능 저하가 발생한다.

 

재귀 함수의 예시(팩토리얼)

Basic rule:
	N <= 1 이라면, n =1
Inductive rule:
	N > 1, n! = n * (n-1)! 
    

int factorial(int n){
	if(n <= 1)		//Basis part
 		return 1;
	else			//Inductive part
		return n * factorial(n-1);
}

5! = 5 x 4 x 3 x 2 x 1입니다.

5! = 5 x 4!으로 볼 수 있습니다.

4! = 4 x 3!으로 볼 수 있습니다.

이렇게 n! = 자기 자신(n) x (n-1)!으로 볼 수 있기 때문에 위와 같이 재귀 함수로 만들 수 있습니다.

 

반복문의 예시(팩토리얼)

int n = 5;
int sum = 1;
for(int i = n; i>0; i--){
	sum = sum * i;	
}

위와 같이 반복문을 통해서도 구현할 수 있습니다.

 

피보나치수열을 재귀로 구현

이전의 두 수 합을 다음 항으로 하는 수열을 피보나치 라 합니다.

0, 1, 1, 2, 3, 5, 8, 13,.....

 

피보나치수열의 i번 째 값을 계산하는 함수 F를 정의하면 다음과 같습니다.

F0 = 0, F1 = 1

F(i) = F(i-1) + F(i-2)

 

위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀 함수로 구현할 수 있습니다.

statif int fibo(n){
	if(n<=1)
		return n;
	else
		return fibo(n-1) + fibo(n-2);
}

 

반복문을 재귀로 바꿔보겠습니다.

반복문

static int arr[] = {10, 20, 30};

private static void printArray(){
	for(int i=0; i<arr.length; i++){
		System.out.print(arr[i] + "\t");    
	}
	System.out.println();
}

재귀

static int arr[] = {10, 20, 30};
private static void printArray(int length){
	System.out.print(arr[length] + "\t");
	if(length==0) return;
	printArray(length-1);
}

 

n개 중 k개를 뽑는 조합의 경우를 재귀로 작성해보자

수학적으로는 다음과 같이 표현할 수 있습니다. (nCk = n! / (n-k)! * k!)

3C2는 3개 중에 2개를 뽑아옵니다.

 

A B C 중에 2개를 뽑아오는 경우의 수를 구하려면 어떻게 할까요?

A, B, C에 대하여 우리는 뽑거나 뽑지 않거나 둘 중에 한 가지를 선택합니다.

만약 A를 뽑았다면 그 뒤에 1개를 뽑아야 하고 올 수 있는 건 B와 C입니다.

만약 A를 뽑지 않았다면 그 뒤에 2개를 뽑아야 하고 올 수 있는 건 A와 C입니다.

 

A B C.... N 중에 r개를 뽑아오는 경우의 수를 구하려면 어떻게 해야 할까요?

만약 N을 뽑았다면 우리는 그 뒤에 r-1개를 뽑아야 합니다. (n-1) C (r-1)

만약 N을 뽑지 않았다면 우리는 그 뒤에 r개를 뽑아야 하고 (n-1) C r 

모든 경우의 수 = (n-1) C (r-1) + (n-1) C r  = n C r

 

n! = n * (n-1)! 와 비슷한 모습이 만들어지지 않았나요?

Inductive에 대해 알게 되었으니 이제 종료 조건인 basis part를 찾아야 합니다.

예를 들어, 3개중에3개를 뽑아야 한다면 경우의 수는 1개입니다.

예를 들어, 3개 중에 0개를 뽑아야 한다면 경우의 수는 1개입니다.

 

순열과 조합에 대한 자세한 설명과 코드는 다음 링크에서 보실 수 있습니다.

https://junuuu.tistory.com/109

 

 

하노이의 탑을 재귀를 통해 풀어보겠습니다.

세 개의 기둥과 다른 크기의 N개의 원판으로 구성됩니다.

어떠한 시작 기둥으로부터 원판을 세 번째로 모두 옮겨야 합니다.

원판을 옮길 때는 반드시 한 번에 한 개씩 옮길 수 있습니다.

옮기는 과정에서 절대로 큰 원판이 작은 원판 위에 놓이지 않아야 합니다.

 

시작 기둥을 from 목적 기둥을 to라고 지칭하겠습니다.

 

자신이 할 수 있는 일  + 나머지(재귀)로 구분하는 것이 중요합니다.

 

하나씩 옮기는 것을 생각하는 순간 머리가 복잡해집니다.

 

3개의 원판을 맨 밑의 원판(3)과 나머지 덩어리 탑(1,2)으로 보면 됩니다.

그리고 나머지 덩어리 탑 또한 맨 밑의 원판(2)과 나머지 덩어리 탑(1)으로 생각합니다.

 

이렇게 생각해 보았을 때 나머지 덩어리 원판들(1, 2)은 임시 기둥에 두어야 하고, 맨 밑의 원판(3)은 목적지(to)로 이동하고 임시 기둥에 있던 원판들을 목적지(to)로 이동시켜야 합니다.

 

임시 기둥에 있던 원판들을 목적지로 이동시킬 때는 처음에 했던 과정과 동일하게 (1) 원판을 다른 기둥으로 옮기고 맨 밑의 원판(2)은 목적지(to)로 이동시킵니다.

 

이제 덩어리가 1개가 된다면 이는 맨밑의 원판(1)이므로 바로 목적지(to)로 이동시킵니다.

 

이렇게 덩어리들이 이동하면서 시작 기둥과 temp기둥이 계속 변하게 됩니다.

 

처음에는 다음과 같이 구성되어있습니다.

from, temp, to

하지만 맨 밑 원판 to로 옮긴 이후에는

나머지 덩어리들은 temp로 이동해있기 때문에 다음 재귀 호출에는 from = temp가 되고 temp = from이 됩니다.

temp, from, to

 

또한 덩어리 원판들을 이동시킬때는 from, temp, to에서 to로 이동시키는 것이 아니라 temp로 이동시켜야 하므로 from, to, temp가 됩니다.

 

이를 구현해보자면 아래와 같습니다

public static void hanoi(int n, int from, int temp, int to) {
	if (n == 0) {
		return;
	}
	// n-1 원판 이동(덩어리)
	hanoi(n - 1, from, to, temp);
	// n번 원판 이동(맨밑의 원판)
	System.out.println(n + " : " + from + " -> " + to);
	// n-1개 원판(덩어리 원판 이동)
	hanoi(n - 1, temp, from, to);
}

 

https://swycha.tistory.com/133

[알고리즘] 순열과 조합 (java)