[알고리즘] 반복과 재귀, 팩토리얼 재귀 함수, 하노이탑

반복(Iteration)과 재귀(Recutsion)

반복과 재귀는 유사한 작업을 수행한다.
반복문으로 코드로 구현한 것을 재귀식으로도 구현할 수 있다.

반복

반복은 수행하는 작업이 완료될 때까지 계속 반복하는 것으로 보통 for문 while문 구조

재귀

재귀는 자신을 정의할 때 자기 자신을 재참조하는 것을 의미한다.
재귀함수는 함수내부에서 자기 자신을 계속적으로 호출하면서 풀어가는 함수이다.

재귀 예제1 : 팩토리얼 함수

java factorial 재귀 함수 실행코드

int fact(int n){
	if(n<=1) 
    	return 1;
   	else 
    	return n * fact(n-1);
}

재귀 예제2 : 하노이탑

하노이의 탑(Tower of Hanoi)은 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 원판의 크기 순서대로 쌓여있다. 하노이탑 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다.

1. 한 번에 한개의 원판만 옮길 수 있다.
2. 큰 원판이 작은 원판 위에 있어서는 안 된다.

java 하노이탑 실행코드

/*
	N : 원판의 개수
	from : 출발지
	temp : 옮기기 위해 이동해야 장소
	to : 목적지
*/

void Hanoi(int N, int from, int temp, int to) {

    // 이동할 원반의 수가 1개라면?
	if (N == 1) {
		print(from + " " + to + "\n");
		return;
	} 

    /* A -> C로 옮긴다고 가정할 떄,
	STEP 1 : N-1개를 A에서 B로 이동
    (= from 지점의 N-1개의 원판을 temp 지점으로 옮긴다.)*/
	Hanoi(N - 1, from, to, temp); 

    /*STEP 2 : 1개를 A에서 C로 이동 
    (= from 지점의 N번째 원판을 to지점으로 옮긴다.)*/
	print(from + " " + to + "\n");

    /*STEP 3 : N-1개를 B에서 C로 이동 
    (= temp 지점의 N-1개의 원판을 to 지점으로 옮긴다.)*/
	Hanoi(N - 1, temp, from, to);
}