왜 정상 재귀 함수가 성공적으로 실행되는 입력에 대해 꼬리 재귀 함수가 실패합니까?

Question

MSDN 설명서에 따라 재귀 함수를 작성하는 동안 accumulator 인수를 사용하면 함수가 꼬리 재귀 적으로 만들어 스택 공간이 절약됩니다. 나는 꼬리가없는 목록 -

먼저 모든 숫자의 합으로 계산 MSDN 사이트에서 주어진 두 가지 예를 사용하고 는

let rec Sum myList = 
    match myList with 
    | [] -> 0 
    | h::t -> h + Sum t 

을 recursion- 지금 꼬리는

let Sumtail list = 
    let rec loop list acc = 
     match list with 
     | h::t -> loop t acc + h 
     | [] -> acc 
    loop list 0 

을 recursion-

및 입력 [1..100000]의 두 기능을 모두 실행하십시오. 함수 Sum이 목록의 합계를 계산하지만 [1..1000000] 을 전달하지만 두 번째 함수 Sumtail이 [1..100000]에서 실패하면 tailoverflow 예외가 발생하지만 꼬리 재귀를 사용하므로 첫 번째 함수는 더 나은 성능을 제공해야합니다. 재귀 함수에 영향을주는 다른 요인이 있습니까?

Answer 1

loop t acc + h이 (loop t acc) + h으로 해석되어 +이 loop의 마지막 연산이되도록하기 때문에 두 번째 함수는 꼬리 재귀가 아닙니다.

기능이 꼬리 재귀가되도록 loop t acc + h에서 loop t (acc + h)으로 변경하십시오.