재귀에 어설픈 생퀴들을 위한 세번째 이야기야. 오늘은 늬들이 흔히 잘못알고 있는 스택오버플로우 이야기니까 잘 보도록.


지금까지 살펴본 재귀는 자연재귀라고 불른다. 수학적 귀납법 같은거라 쉽게 이해가 되는 구조야. 예를 들면


defn collect-even [nl]

  if (empty?(nl))

    []

    let n = first(nl)

    if even?(n)

       push(n, collect-even(rest(nl)))

       collect-even(rest(nl))


위의 재귀가 [0 1 2 3 4 5]에 대해 실행되면 이런식이 된다.


collect-even([0 1 2 3 4 5])

=> push(0, collect-even([1 2 3 4 5]))

==> push(0, collect-even([2 3 4 5]))

===> push(0, push(2, collect-even([3 4 5])))

====> push(0, push(2, collect-even([4 5])))

=====> push(0, push(2, push(4, collect-even([5]))))

<===== push(0, push(2, push(4, collect-even([]))))

<==== push(0, push(2, push(4, [])))

<=== push(0, push(2, [4]))

<== push(0, [2 4])

<= [0 2 4]


뭔가 쭈욱 늘어났다가 다시 줄어들었지? 중간에 아직 답을 모르고 끝까지 가봐야 답을 거꾸로 다시 낼 수 있기 때문에 저 현상이 일어난다.

저런식의 재귀는 중간에 생기는 나중에 결과를 알아내야 하는 임시값들을 저장하기 위해서 스택을 쓰고, 재귀가 많이 일어나면 스택이 부족하게 되서 스택오버플로우가 일어날 수 있다.


니들이 흔히 들은 "재귀는 스택오버플로우 어쩌고 저쩌고" 이게 저 문제야.

이 문제를 해결하는 방법은 두가지야. 하나는 스택오버플로우가 일어나지 않는 한도 내에서만 저런식의 재귀를 쓰는거고, 다른 하나는 근본적인 해결 방법인 꼬리재귀로 바꾸는 거야


위의 예를 꼬리 재귀로 바꾸면:


defn tail-collect-even [nl, result]

  if (empty?(nl))

    result

    let n = first(nl)

    

    if even?(n)

      tail-collect-even(rest(nl), push(n, result))

      tail-collect-even(rest(nl), result)


defn collect-even [nl]

  tail-collect-even(nl, [])


collect-even([0 1 2 3 4 5])

=> tail-collect-even([0 1 2 3 4 5], [])

=> tail-collect-even([1 2 3 4 5], [0])

=> tail-collect-even([2 3 4 5], [0])

=> tail-collect-even([3 4 5], [0 2])

=> tail-collect-even([4 5], [0 2])

=> tail-collect-even([5], [0 2 4])

=> tail-collect-even([], [0 2 4])

<= [0 2 4]


먼저 것과 비교해보면 그냥 인자 하나가 줄고 다른 하나는 느는 모양이고 중간 계산값이 없어.

마지막 꼬리 부분에서 다른 연산의 일부가 아닌 독고다이 함수콜 형태의 재귀가 일어나기 때문에 이런 재귀를 꼬리재귀 라고 불러. 이러한 재귀는 꼬리재귀 최적화를 지원하는 컴파일러에서 컴파일러가 단순 반복문으로 바꿔서 컴파일하지(대부분 컴파일러가 지원한다. 안하면 바꿔). 

사람은 사람이 편한 식으로 생각하고 컴파일러가 효율적으로 실행 할 수 있도록 컴파일하자는 아이디어지.


니가 재귀로 프로그래밍 하고자 할때는 꼬리재귀를 하면 스택오버플로우를 피할 수 있다. 


어떤 생퀴들은 반복으로 되기 때문에 재귀 안한다는데, 자기참조와 상호참조가 동시에 일어나는 문제들은 반복으로 바꾸려면 머가리 빠게지고 유지보수 하기도 존나 빡쳐.


세종류의 꼬리재귀 형태만 잘 알면 재귀가 일어나는 문제는 다 풀수 있지. 앞으로는 여기에만 집중해서 자기참조와 상호참조가 동시에 일어나는 문제들만 집중적으로 재귀로 만들어 볼꺼야