투명한 기부를 하고싶다면 이 링크로 와보세요! 🥰 (클릭!)
바이낸스(₿) 수수료 평생 20% 할인받는 링크로 가입하기! 🔥 (클릭!)
지난번엔, 함수가 프로그램을 구성하는 기본적인 블록이라는것을 알게 되었다.
이번 글에서도 여전히 함수에 대해서 다뤄볼 것이다.
몇몇 방법을 통해 함수들을 구성하고, 합성하는 방법에 대해 알아보며, 마지막으로 다음 글에서 데이터와 객체에 대해 알아본다.
이번에는 재귀를 다시 살펴본다.
재귀를 표현하는 여러 방법이 있다는 것을 알게 될 것이다.
리뷰 할 겸 함수 application을 살펴보자. f(e1,...en)을 계산할 때에 있어서 다음의 규칙을 따른다.
- e1~en을 먼저 계산한다.
- 함수 f의 body로 application 부분을 대체한다.
- 파라미터 v1,...,vn을 f의 파라미터로 바꾼다.
이것은 프로그램 자체를 다시 작성하는 것으로 형식화 될 수 있다.
f(x1 , ... , xn)의 경우 f(v1 , ... , vn)으로 대체되며 이를 [v1/x1, ... , ]B 의 형태로 다시 적어볼 수 있다. (x1이 v1으로 대체된다는 의미)
[v1/x1, ... , vn/xn]을 substitution(대체)라고 한다.
위의 GCD 알고리즘의 경우 아래와 같이 rewrite(재작성)된다.
아래와 같은 예시도 있다.
위 두 예시에 대한 차이점이 무엇인가?
GCD는 호출을 통하면 본질적으로 내부의 값은 다르지만 같은 식으로 돌아간다.
그치만 factorial의 경우 표현식 자체가 계속해서 길어지는 것을 볼 수 있다.
이에 따른 재작성 규칙의 차이가 실제 컴퓨터의 실행 차이로 직접 변환된다. 실제로 자기 자신을 마지막 작업으로 다시 호출하는 재귀 함수가 있으면, 해당 함수의 stack 프레임을 재 사용할 수 있다. (a -> a'를 호출할때 a는 더이상 사용되는 변수가 없다면 날려버릴 수 있으니까!) 이를 통해 꼬리 재귀(Tail recursion)가 일정한 고정 공간(재사용되는 단일 공간)에서 실행될 수 있음을 알 수 있다. 이는 stack overflow를 방지할 수 있게 해 준다.
스칼라의 경우 @tailrec이라는 어노테이션으로 해당 함수가 tail recursive가 아닐 경우 에러를 띄워줄 수 있다.
반면에, 아까 factorial의 예제를 보면 factorial을 호출하여 반환값을 받은 후에 여전히 해야 할 작업이 남아 있는 것을 볼 수 있다.
n을 곱해야 한다. 그렇기 때문에 tail recursive call이 아니게 되는 것이다.
다른 함수를 그 중에 호출하느냐, 그렇지 않느냐는 중요하지 않다. 다만 마지막에 stack frame을 털어버리면서 재귀를 호출할 수 있느냐는 점이 중요한 것이다.
요롷게 하면 쌉가능.
