어음 아래 블로그 쓰는 게이인데 그 뭐냐 여기다 글이랑 올려 보라고 그래가지고...

이제 막 C나 C++ 책 한권 막 끝내고 뭐 볼까 하는 형들에게 맞는 거 같다. 내가 막 그러고 있는 차라서..

네이버 블로그에 슬기로운 백수생활 치면 나옴.

글은 열심히 쓰는데 피드백이 없어서 방향성 잃고 막 그러는 중임 댓글 태클 뭐든 환영 ㅜ ㅜㅋ


------------------------------------------------------------------------------------------------------------------------------------------------


재귀. 설명을 통해 이해하는 것 말고는 재귀를 한마디로 딱 부러지게 설명할 수 있는 게 없는 것 같지만 그래도 한마디로 표현해 보자면 함수가 자기 자신을 한 번 더 호출하는 것이다.(띠용~) 그 이유는 당연히 그 함수가 가지고 있는 기능이 한 번 혹은 그 이상이 필요하기 때문이다.


재귀를 설명하는 것에 빠지지 않는 하노이탑을 보기 전에 보다 이해하기 쉽고 써먹기 좋은 RPG 게임의 레벨업 과정을 살펴보자.

캐릭터에게 경험치가 들어오면 렙업 경험치에 도달했는지 살펴보아야 할 것이다. CheckUp 함수는 기존에 있는 경험치와 들어온 경험치를 합하고 렙업 경험치에 도달했는지 점검한 뒤에 레벨을 올린다. 이대로가 끝인가? 그렇지 않다.


고인물 성기사의 버스를 타는 저렙 법사가 있다고 가정해 보자. 이 법사는 다음 레벨업 경험치는 100이고 그다음 레벨업 경험치는 120이다. 첫 전투에서 경험치 100,000짜리 몬스터를 잡았을 경우 레벨업을 한 번만 처리해서는 안 될 것이다. 그럼 레벨을 하나 올리고 나서 남은 경험치가 레벨업 수준인지 다시 한번 점검해야 할 것이다. 그렇다. 레벨업의 마지막 순간에 자기 자신을 한 번 더 호출하면 된다. 이는 다음처럼 아주 간단하게 구현할 수 있다.

int level = 1; int currentExp = 0; // int는 경험치를 담기에는 작은 자료형이다. int levelupExp = 100; void CheckUp(int exp) ( currentExp += exp; if(currentExp >= levelupExp) { level++; exp = currentExp - levelupExp; currentExp = 0; levelupExp *= 1.2f; CheckUp(exp); } }

간결하고 깔끔한 느낌이 좀 오는가?

다른 예로 거듭제곱을 들 수 있다. 거듭제곱은 자기 자신을 계속 곱하는 것이다. 자기 자신을 계속 곱한다? 그렇다 자기 자신을 곱하는 것을 함수로 만들어 계속 호출하면 되는 것이다. 이쯤 되면 확실하게 감을 잡았으리라 생각된다. 다음은 그것을 코드로 나타낸 것이다.

int Pow(int no, int times) { if(times == 0) return 1; // 모든 횟수가 끝났다면 끝낸다. else no * Pow(x, times - 1); // 그게 아니라면 자신을 한번더 호출해 제곱을 시킨다. }

다음의 그림을 보면 보다 확실해진다. x가 들어가면 -1이 되는 방이 있다. 이곳에는 갈 수 있는 길이 두 개가 있는데 하나는 조건이 맞아야 열리는 문과 아래로 내려가는 구멍이다. x는 탈출하기 위해서 구멍을 통해 계속 내려가고 결국 조건에 맞아 문이 열리고 탈출에 성공한다는 그림이다.


보면 for 루프의 다른 형태처럼 보이기도 할 것이다. 실제로 for 루프 문으로 다 구현이 가능하다. 그래서 어떤 것으로 구현하는 것이 나은지 for vs 재귀라는 제목으로 두 개의 장단점을 비교하는 글들도 많이 있다. 간단히 살펴보면 재귀의 유일한 장점은 코드가 간결해져 가독성이 매우 높아진다는 것이다. 그것 외에는 죄다 for 루프에 비해 안 좋다.


이유는 후에 다루기도 하겠지만 함수를 호출하면 함수의 포인터들이 스택에 차곡차곡 쌓이게 된다. 게다 함수가 끝나야 사라지는 지역 변수들도 함수와 함께 메모리에 쌓이게 된다. 그렇게 되면 오래 지나지 않아 스택 오버플로가 발생하고 프로그램이 폭파되기도 하는 것이다. 반면에 for 문은 변수들을 몇 개 더 사용하게 되지만 매 루프마다 블록안의 사용한 변수들이 지워지고 새로 생기고 하면서 일정 크기를 유지한다. 재귀는 예측이 어려운 함수 포인터 등과 같은 여러 문제들 때문에 오버헤드가 생겨 속도 면에서도 for 문이 유리하다.


그렇다면 자신의 이름을 제목으로 쓰이는 이 글에서조차 신나게 까이고 있는 재귀는 언제 써야 할까? 깊이를 예측 가능하고 크게 벗어나지 않는 경우에 쓸 수 있다. 이렇게 썼지만 와닿지도 않고 재귀는 안 좋은 것으로만 여겨져 머지않아 잊혀질 것을 알고 있다. 하지만 걱정 말 자 그렇게 잊고 있다가도 이 글을 읽고 나면 마치 잊었던 악상이 다시 떠오르는 것처럼 언젠가 오! 이건 재귀이여만 해! 할 때가 온다.


마지막으로 재귀하면 빠지지 않는 하노이의 탑이다.


하노이의 탑은 100여 년 전 에드워드 루커스라는 수학자가 만들어 낸 것으로... 블라... 블라... 블라...


규칙

왼쪽에 있는 접시들을 오른쪽으로 옮기는 것인데 다음과 같은 두 가지 큰 규칙이 있다.

1. 작은 접시 위에 큰 접시가 놓일 수 없다.

2. 접시는 한 번에 하나씩만 옮길 수 있다.

3. 모든 접시는 옮기기 전에 기둥에 꼽혀 있어야 한다.


풀이

정답은 접시를 옮기는 것에 다음에 오는 그림처럼 총 7회가 걸린다.


게임의 규칙은 이것으로 되었을 거라고 본다. 그런데 이것은 생각보다 쉽게 구현이 되지 않는다. 앞서 살펴본 것들과 다르게 단순하게 반복되는 것이 아니기 때문이다. 과연 무엇이 반복되는가? 이건 위에 것만 가지고는 잘 보이지 않는다 그럼 다음 그림으로 접시 4개의 예를 간단히 살펴보자.


그렇다. 가장 아래의 것을 옮기려면 위의 접시들이 2번 기둥으로 먼저 모두 이동해야 한다는 것이다. 접시 3개를 옮길 때도 위의 과정은 있었다. 쉽게 보이지 않았을 뿐이다. 이 과정을 다음처럼 정리할 수 있다.


1. n 번째 위의 접시들, n-1개의 접시들을 기둥 2번 기둥으로 옮긴다.

2. n 번째 접시를 기둥 3번으로 옮긴다.

3. 기둥 2에 있는 n-1개의 접시들을 기둥 3으로 옮긴다.


하노이 탑의 규칙 중 하나가 한 번에 하나씩만 옮길 수 있는 것이다. 위의 과정들 중 1번이나 3번에 n-1개의 접시들을 옮긴다고 되어 있지만 한 번에 옮길 수 없으니 n번째 위의 접시들을 하나씩 옮겨야 하는데 바로 여기서 재귀가 쓰이게 되는 것이다. n-1개의 접시들을 옮기는 과정은 다음과 같다.


1. n-1 번째 위의 접시들, n-2개의 접시들을 기둥 2번으로 옮긴다.

2. n-1 번째 접시를 기둥 3번으로 옮긴다.

3. 기둥 2에 있는 n-개의 접시들을 기둥 3으로 옮긴다.


이 알고리즘을 의사 코드로 표현하면 다음과 같다.

HanoiFunc( n, start, destination, open) { HanoiFunc(n - 1, start, open, destination) MoveFunc(n, start, destintion) HanoiFunc(n - 1, open, destination, start) }

매개 변수는 4개인데 접시의 개수, 시작하는 기둥의 번호, 대상이 되는 기둥의 번호, 접시를 놓을 수 있는 기둥(자신보다 작은 것의 경우 갈수 없다)의 번호이다.


탈출 조건

앞서 작성한 의사 코드는 계속 자기 자신에게 n-1을 해서 호출하게 된다. n이 -가 되어도 탈출할 방법이 없는 것이다. 스택이 가득 차 프로그램이 터질 때까지 계속 달리게 될 것이다. 탈출할 수 있는 문을 만들어 줘야 한다! 말은 이렇게 했지만 방법은 매우 간단하다.

HanoiFunc( n, start, destination, open) { if(n <= 0) return; HanoiFunc(n - 1, start, open, destination) MoveFunc(n, start, destintion) HanoiFunc(n - 1, open, destination, start) }


블로그에서 계속...