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

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

다음의 단계를 거친다.

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

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

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

예제 코드

• Python code : Factorial.py

• Java code : Factorial.java

• Cee code : Factorial.c (TailRecursion 포함)

• Lisp code : Factorial.lisp

• Ruby code : Factorial.rb

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

그외의 사용된 Algorithm들.

• DynamicProgramming

• ViterbiAlgorithm

유사한 DesignPatterns

• DecoratorPattern

• CompositePattern

SeeAlso RecursiveFunction