재귀 BNF

{rec {<id> <Expr>} <Expr>}

이렇게 생겼다.

id는 재귀 정의할 이름

그 옆의 Expr은 재귀의 body

마지막 Expr은 재귀를 사용하는 부분

 

다음은 팩토리얼 함수를 정의한거다

{rec {fact {fun {n} {if0 n 1 {* n {fact {- n 1}}}}}} fact}

fact가 id에 해당한다.

fun에서 n을 받아 n의 팩토리얼을 계산한다.

 

팩토리얼은 다음과 같이 표현할 수 있다

n! = n * (n - 1)!

그렇기 때문에 {* n {fact {- n 1}}}이 들어간거다

{- n 1}에서 n에서 1을 뺀 값을 인자로 넘겨서 fact를 다시 호출한다.

 

 

이제 다양한 인자를 받는 재귀문에 대한 콘크리트 문법을 살펴보자

{with {fac 
       {fun {n} 
         {with {facX 
                {fun {facY} 
                  {fun {n} 
                    {if0 n 
                         1 
                         {* n {{facY facY} {- n 1}}}}}}}
          {{facX facX} n}}}}
 {fac 10}}

 

facX는 함수 자체를 인자로 받고,

facY를 통해 자기 자신을 반복 호출한다. 

 

이 방식의 장점은 함수를 고차 함수로 만들고 재귀 호출을 유연하게 사용할 수 있다.