Какая из этих функций рекурсивна?

Question

let rec f1 = fun x -> if x = 0 then 1 else f1 (f1 0) in ... 

let rec f2 = fun x -> if x = 0 then foo x else f2 x in ... 

где Foo не хвостовая рекурсия

let rec f3 = fun x -> if x = 0 then foo x else f3 x in ... 

где Foo является хвостовой рекурсией

Answer 1

Все они являются хвостовой рекурсией.

f1 однако содержит два рекурсивных вызова, из которых только внешний - это хвостовой вызов.

Для f2/f3, это не имеет значения, является ли foo хвостовой рекурсией или нет, потому что она не является частью рекурсии f2/f3 на всех.

Answer 2

Вы не должны спрашивать, является ли функция хвостовой рекурсивной. Вы должны спросить, являются ли все вызовы хвостовыми вызовами. Кроме того, является ли foo хвостом рекурсивным или нет, фактически не имеет значения - хвостовой вызов является хвостовым вызовом, независимо от того, какую функцию он вызывает.

Итак, давайте их по одному за раз:

let rec f1 = fun x -> if x = 0 then 1 else f1 (f1 0) in ... 

В else внутренний вызов f1 не хвост вызова. Внешняя. Обратите внимание, что это означает, что в зависимости от того, как вы определяете этот термин, вы можете сказать, что эта функция равна хвост рекурсивный (у него есть хвостовой вызов для себя) или что это не так (у него есть не-хвост для вызова сам).

Вот почему важно сосредоточиться на , которые звонят в хвост, а не хвост рекурсии! Язык с устранением хвоста вызовет это для внешнего вызова, но не для внутреннего.

let rec f2 = fun x -> if x = 0 then foo x else f2 x in ... 
let rec f3 = fun x -> if x = 0 then foo x else f3 x in ... 

Призывы к foo и к f2 являются хвост вызывает в обоих случаях. Опять же, неважно, что такое foo.