열혈 자료구조 2

참고문헌 - 윤성우 <윤성우의 열혈 자료구조>

♨ 개인적 해석이 들어간 글임으로, 인지하지 못한 오류가 있을 수 있습니다 ♨

 

Chapter 2. 재귀(Recursion)

2-1. 함수의 재귀적 호출의 이해

▣ 재귀함수의 기본적인 이해

 재귀함수는 함수 내에서, 함수가 완료되기 전에 해당 함수를 다시 호출하는 것이 아니라

 함수의 서로 다른 복사본들이 호출되는 것이다

요런 느낌으로 당사자는 뒤에 있고 복사본이 호출 -> 복사본을 호출 -> 복사본을 호출 ... 의 반복이다

즉, 재귀함수가 처음 호출될 때부터 당사자가 아닌 복사본을 호출하는 것이다

 

함수를 구성하는 명령문은 CPU로 이동되어(복사가 되어서) 실행이 된다

그런데 이 명령문은 얼마든지 CPU로 이동(복사) 가능하다

따라서 재귀 함수의 중간쯤에 위치한 명령문을 실행하다가(재귀함수가 완료되지 않은 상태에서)

다시 동일한 이름의 재귀함수의 앞 부분에 위치한 명령문을 CPU로 이동시킬 수 있다

그래서 재귀적인 형태의 함수호출이 가능한 것

 

재귀함수 예)

Recursive 함수는 재귀함수로 0이하의 인자를 입력받을 때까지 반복해서 호출된다

위 코드 상에서 인자 3이 입력되고 함수가 완료되기 전 2(3-1)을 인자로 받는 Recursive가 호출된다

이같이 반복되다 인자가 0이 입력되는 순간 탈출조건(if문)에 의해 함수가 종료되고

연쇄적으로 호출된 자리의 함수가 종료된다

마지막으로 처음 호출된 Recursive(3)이 종료되면서 마무리된다

 

위 내용을 도식화 해보면 아래와 같다

보듯이 재귀함수에서 제일 중요한 부분은 탈출조건(if와 같은 조건문)이 되시겠다

 

 

▣ 재귀함수의 디자인 사례

재귀함수는 자료구조나 알고리즘을 단순화되는데 사용되는 중요한 무기다

특히 재귀적 수학식을 그대로 코드로 옮길 수 있다

예) 팩토리얼(factorial) 코드로 나타내기

팩토리얼 n! = n × (n - 1) × ··· × 2 × 1

                = n × (n - 1)!

      ∴ f(n) = n × f(n-1) (단, n = 0이면, f(n) = 1)

 

완.벽

 

2-2. 재귀의 활용

▣ 피보나치 수열

피보나치 수열은 재귀적인 형태를 띄는 수열이다

피보나치 수열의 정의는 "앞서 나온 두 수를 더해서 현재의 수를 만드는 수열"이다

그렇기 때문에 처음과 그 다음(두 번째) 수는 0과 1로 주어진다

수학식으로 표현하자면

이거 비슷하게 되겠다

이를 코드로 표현하자면

 

▣ 이진 탐색 알고리즘의 재귀적 구현

이진 탐색 알고리즘의 논리 자체는 재귀적이기 때문에 이 역시 재귀함수로 표현할 수 있다

앞선 chapter에서 나온 이진 탐색 알고리즘의 반복 패턴은 다음과 같다

 

 1. 탐색 범위 중앙에 목표 값이 저장되었는지 확인

 2. 저장되지 않았다면 탐색 범위를 반으로 줄여서 다시 탐색 시작

 

이 반복 패턴에서 벗어나는 경우는 두 가지로

① 탐색 목표를 찾았을 때

② 탐색에 실패 했을때 (탐색 범위의 시작점이 범위 마지막 지점 보다 커질때)

 

이진 탐색 알고리즘을 재귀함수로 표현하였을때, ②의 조건이 재귀함수의 탈출 조건이 된다

 

재귀함수로 표현한 이진 탐색 알고리즘

 

 

2-3 하노이 타워 : The Tower of Hanoi

▣ 하노이 타워 문제의 이해

재귀함수를 잘 활용할 수 있는 대표적인 예가 하노이 타워라고 한다더라

(재귀적으로 접근하지 않으면 해결이 쉽지 않다더라)

 

하노아 타워 문제는 세 개의 막대 중 하나의 막대에 쌓여있는 서로 크기가 다른 원반을, 다른 막대에 이전의 모습대로 옮기는 방법에

관한 것 이다

 

이때 막대를 옮기는 조건이 있는데

① 원반은 한 번에 하나씩만 옮길 수 있다

② 작은 원반 위에 큰 원반이 올라올 수 없다

 

위의 규칙들을 지키면서 막대 A(원반이 원래 있던 막대)에서 막대 C(원반이 옮겨져야 할 목적지)로 옮기는 것이다

 

Feat 킹림판 3D

위 그림을 보면서 문제를 풀려고 할 때,가장 먼저 생각되는 것은 원판 3이 C에 가장 먼저 와야한다는 것이다

3번이 움직이기 위해서는 2번이, 동일한 이유로 1번이 움직여야한다

보다 정확히 설명하자면, 1번과 2번이 A에 있는 순서 그대로 B에 있어야 3번 원판이 C로 움직일 수 있다는 것이다

 

▣ 하노이 타워의 반복패턴 연구

원반이 4개일 때를 생각하면서 하노이 타워 문제 해결의 반복 패턴을 알아보자

 

 

 

①기본세팅 : 가장 큰 원판 4를 C로 보내야 시작할 수 있다

② 1~3 -> B : 4번을 움직일 수 있게 1번부터 3번까지 원판이 B로 이동 (과정은 중략)

③ 4 -> C : 4번이 C로 왔다 이제 3 -> 2 -> 1 순으로 오면 문제 해결이다

④ 해결 : 했다

 

위의 과정을 3단계로 글로 표현하면 아래와 같다

1. 옮기려는, 가장 큰 원판(4)보다 작은 모든 원판(1~3)을 B로 옮긴다

2. 자유로워진 가장 큰 원판을 C로 이동시킨다

3. B에 있는 원판들을 C로 옮긴다

 

이를 일반화 하여 막대 A에 꽂혀있는 원반 n개를 막대 C로 옮기는 과정을 표현하면

1. n-1개의 원반을 A에서 B로 이동

2. n번 원반을 A에서 C로 이동

3. B에 있는 n-1개를 C로 이동

 

 

▣ 하노이 타워 문제의 해결

위의 일반화된 문장을 코드로 작성해보자

 

일단 함수의 파라미터로 필요한 것은

 - 원판의 갯수(n)

 - 기둥 3개 (A: 있던 자리, B : 거쳐가는 자리, C : 목적지)

또한 재귀함수에서 가장 중요한 것은 탈출조건이다

옮기는 행위를 멈추는 조건은 움직일 원반이 남아있지 않을때이다

즉, 마지막 1개 남은 원반을 움직이는 것으로 함수가 종료되어야 한다

 

이제 이전에 일반화했던 막대를 옮기는 과정을 코드로 표현해보자면

첫 번째 (HanoiTop(num - 1, from, to, by))과 기본 함수와의 차이는 by와 to의 위치가 바뀌어 있다는 것이다

이는  n-1개의 원판이 to(C)로 가는 것이 아니라 by(B)로 가는 것이기 때문이다

두 번째 (cout~)는 1개 남은 n번 원판을 움직이는 것이기 때문에 바로 처리를 한 것이고

마지막 (HanoiTop)은 by(B)에 있던 n-1개의 원판이 to(C)로 움직이는 것을 재귀함수로 처리한 것이다

 

다 합쳐서 본다면 아래와 같다