재귀용법. ComputerScience에서 각종 Algorithm등에 유용하게 활용되는 기법으로, 자기자신을 호출하도록 설계하는 방법.

문제를 자신보다 점점 더 작은 인스턴스들로 정의할 수 있게 하는 강력한 원리

다음의 단계를 거친다.

  • 감기단계(winding) : 계속적으로 자신을 호출
  • 종료조건도달
  • 풀기단계(unwinding) : 최초의 호출이 리턴될때까지

Cee의 경우 내부적으로 Stack을 생성한다. Stack의 후입선출특성이 함수의 호출종료순서와 잘 맞는다. 그러나, Recursion이 많은 프로그램의 경우 관련정보를 계속 유지해야하므로 많은 메모리를 사용한다. 일반적인 Stack레코드는 크기가 크기때문에 더욱 시간이 많이 걸린다. 어떤경우에는 이런 부담을 피하기 위해 TailRecursion이라는 특별한 형태를 사용할 수 있다.

가장 흔한 예로 factorial계산 방법이 있다. (실수부분에서의 factorial계산은 StirlingFormula참고)

a! = \left\{ \begin{array}{ll} 1 & \textrm{if a=1} \\ a \times (a-1)! & \textrm{} \end{array} \right

예제 코드

위 계산방법은 신기하게도 잘돌아가고, 성능도 좋다. 잘못쓰면 무한루프에 빠진다. 적절히 끝내는 포인트를 설정해야한다.

그외의 사용된 Algorithm들.

유사한 DesignPatterns


SeeAlso RecursiveFunction

Bhn: Recursion (last edited 2011-08-21 16:48:13 by yong27)

web biohackers.net