2. 재귀

 

이번에는 재귀를 알아보겠습니다.

 

우선 재귀 알고리즘이란 알고리즘 자신을 이용해 정의된 알고리즘을 말합니다. 

그리고 이러한 재귀는 재귀 케이스와 베이스 케이스로 이루어져 있습니다. 

 

작동 원리 : 대기중인 재귀호출을 위한 저장/복구는 컴퓨터에 의해 자동적으로 수행됩니다. 

 

그리고 만약 재귀알고리즘을 짜게 된다면 기본적으로 지켜야할 규칙들이 있습니다. 

기본 규칙 

1. 베이스 케이스를 항상 가져야합니다. 
2. 재귀호출은 항상 베이스 케이스를 향해야 합니다.
3. 저장/복구 때문에 성능이 저하되서 꼭 필요할 때만 써야합니다.

나쁜 재귀 

• 베이스 케이스가 없거나 재귀 케이스가 베이스 케이스로 향하지 않습니다. 
• 따라서 부정확한 결과, 미정지, 기억장소 고갈 등의 문제가 발생합니다. 

---

이러한 재귀알고리즘에서 대표적으로 소개되는 사례는 하노이탑입니다.

하노이탑
초기에 세 개의 말뚝 A B C가 있고 여러개의 원반들이 A말뚝에 쌓여 있습니다. 이 원반들은 C로 옮겨야 합니다. 

조건 
1. 한번에 한 개의 원반만을 이동
2. 언제라도 직경이 큰 원반을 작은 원반 위에 놓지 말것
3. 남은 말뚝을 보조 말뚝으로 사용 가능 

 

하노이탑을 의사코드로 구현해보고 그 의사코드를 통해 c언어로 하노이탑을 구현해보록 하겠습니다.  

Alg hanoi(n)

1. rHanoi(n, 'A', 'B', 'C')

2. return 

 

Alg rHanoi(n, from, aux, to)

1. if(n=1)

       write("move from", from, "to", to)

       return

2. rHanoi(n-1, from, to, aux)

3. write("move from", from, "to", to)

4. rHanoi(n-1, aux, from, to)

5. return 

 

c언어 구현 

여기까지입니다 감사합니다~