✍️ 순환(recursion)
순환(recursion)이란? 알고리즘이나 함수가 수행 도중에 자기 자신을 다시 호출하여 문제를 해결하는 기법
(필자는 '순환'이라는 단어보다는 '재귀'라는 단어가 더 익숙하다.)
순환알고리즘의 구조는 순환을 멈추는 부분과 순환 호출을 하는 부분으로 구성되어 있다.
만약 순환을 멈추는 부분 즉, base condition이 없다면?
시스템 오류가 발생할 때까지 무한정 호출하기 때문에 반드시 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다.
✍️ 순환(recursion) VS 반복(iteration)
컴퓨터에서 되풀이 작업을 할 때 순환과 반복을 사용할 수 있는데 순환은 순환 호출을 이용하고, 반복은 for나 while을 이용한다.
대부분의 순환 알고리즘은 반복 알고리즘과 서로 바꿔 쓸 수 있지만, 하노이 탑의 경우에는 불가능하다.
순환
- 순환적인 문제에서는 자연스러운 방법
- 함수 호출의 오버헤드
반복
- 수행속도가 빠름
- 순환적인 문제에 대해서는 프로그램작성이 어려울 수 있음
✍️ 하노이 탑
막대 A에 쌓여 있는 원판 n개를 막대 C로 옮기는 문제이다. 단, 몇가지 조건을 지켜야 하는데 하노이 탑은 유명하기 때문에 조건 설명은 생략하겠다.
재귀로 풀려면 함수의 정의, base condition, 재귀식 이 3단계를 결정하면 된다.
함수의 정의는 n개의 원판을 막대 A에서 막대 C로 옮기는 방법을 출력하는데 형태는 void hanoi_tower(int n, char from, char tmp, char to)로 한다.
base condition은 n이 1일 때, from에서 to로 원판을 옮기는 것이다.
재귀식은 n-1개의 원판을 막대 from에서 막대 tmp로 옮기는 hanoi_tower(n-1, from, to, tmp), n번 원판을 막대 from에서 막대 to로 옮김을 출력, n-1개의 원판을 막대 tmp에서 막대 to로 옮기는 hanoi_tower(n-1, tmp, from, to)이다.
하노이 탑과 같이 여러 곳에서 자기 자신을 호출하는 형태는 반복으로 바꾸기 어렵다.
