Почему функция хвостовой рекурсии не работает для ввода, для которого нормальная рекурсивная функция выполняется успешно?

Question

В соответствии с документацией MSDN при записи рекурсивной функции использование аргумента аккумулятора делает функцию tail рекурсивной, что экономит пространство стека. Я использую два примера, приведенного на сайте MSDN для расчета суммы всех чисел в list-

первый без хвоста recursion-

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 

и работает как с функциями [1..100000]. Функция Sum успешно вычисляет сумму этого списка, но дает исключение stackoverflow, если я передаю [1..1000000] , но вторая функция Sumtail терпит неудачу при [1..100000], тогда как она должна давать более высокую производительность, чем первая функция, поскольку использует хвостовую рекурсию. Существуют ли другие факторы, влияющие на рекурсивную функцию?

Answer 1

Ваша вторая функция не является хвостовой рекурсией, поскольку loop t acc + h анализируется как (loop t acc) + h, что делает + стать последней операцией на loop.

Измените loop t acc + h на loop t (acc + h), чтобы функция получило функцию tail-recursive.