자료구조 및 실습 - [2] 재귀 (1)

재귀 알고리즘

재귀 알고리즘이란 알고리즘 자신을 사용해 정의된 알고리즘을 말한다. 다시 말해 자기 자신을 알고리즘 안에서 계속 호출하는 것이다. 재귀 알고리즘은 계속해서 자기 자신을 호출하기 때문에 자칫하면 무한루프를 돌 수 있다. 따라서 재귀 함수를 구성할 때에는 두 가지 요소가 필요하다.

재귀 케이스 (Recursion) : 차후의 재귀호출은 작아진 부문제들(subproblems)을 대상으로 이루어진다.
베이스 케이스(base case): 부문제들이 충분히 작아지면, 알고리즘은 재귀를 사용하지 않고 이들을 직접 해결한다

다시 말해 재귀함수는 더 작아지는 방향으로 진행되어야 하고 (베이스 케이스를 향해 진행됨) 베이스 케이스에서는 더 이상 재귀를 사용하지 않고 알고리즘이 종료되어야 한다.

 

---

재귀의 작동원리

재귀의 작동원리를 먼저 그림으로 보자.

재귀함수의 작동원리

재귀의 단계 별 수행을 보도록 하자.

1. 알고리즘을 수행한다.
2. 수행 중 재귀함수가 호출된다.
3. 기존에 수행하던 알고리즘을 완료하지 않고 호출된 재귀 알고리즘을 베이스 케이스까지 수행한다.
4.  베이스 케이스가 종료되면, 이전으로 돌아와 알고리즘을 마저 수행한다.
5. 처음 호출했던 알고리즘이 완료될 때까지 반복해서 돌아간다.

그림에서 볼 수 있듯이 수행 순서는 1->2->3->...->9->10이다. 중요한 것은 또 다른 재귀함수가 호출되면 수행하던 알고리즘을 완료하지 않고 바로 다른 재귀 함수로 넘어간다는 것이다.

 

---

재귀의 기본 규칙

- 베이스 케이스
  베이스 케이스를 항상 가져야 하며, 이는 재귀 없이 해결될 수 있어야 한다.
- 진행방향
  재귀적으로 해결되어야 할 경우, 재귀호출은 항상 베이스 케이스를 향하는 방향으로 진행되어야 한다.
- 정상작동 가정
  모든 재귀호출이 제대로 작동한다고 가정하라!
- 적절한 사용
  꼭 필요할 때만 사용하라, 저장/복구 때문에 성능이 저하되기 때문이다.

앞서 말했듯, 재귀 함수는 계속해서 함수를 호출하기 때문에 종료할 수 있어야 한다. 그러기 위해서는 진행방향이 베이스 케이스를 향해야 하고, 베이스 케이스는 재귀 없이 해결되어야 한다.

또한 재귀함수는 또 다른 재귀함수가 호출되면 수행하던 알고리즘을 완료하지 않고 바로 다른 재귀 함수로 넘어가기 때문에 메모리를 많이 차지하여 성능이 저하될 수 있으므로 적절히 사용해야 한다!

 

베이스 케이스가 존재하지 않거나, 도달할 수 없는 재귀, 또는 재귀 케이스가 베이스 케이스를 향해 가지 않는다면 잘못 설계된 재귀이다. 이는 부정확한 결과, 미정지(nonretmination), 저장을 위한 기억장소 고갈의 영향을 끼친다.