Нет, это не хвостовая рекурсия, потому что foo вызывается из положения хвоста -
function foo(data, acc) {
...
// foo not in tail position here
return foo(data, foo(data, x));
}
Давайте разберемся с этим, используя конкретную программу, такую как fibonacci -
const fibonacci = n =>
n < 2
? n // non tail call!
: fibonacci (n - 2) + fibonacci (n - 1)
console .log (fibonacci (10)) // 55
Выше рекурсивный fibonacci может порождать два вызова на fibonacci, каждый из которых может порождать два больше вызововдо fibonacci.Без переписывания этого невозможно, чтобы оба вызова были в хвостовой позиции.Мы можем обойти эту проблему, используя вспомогательную функцию с дополнительным параметром, then ниже -
const helper = (n, then) =>
{ if (n < 2)
return then (n) // tail
else
return helper (n - 2, a => // tail
helper (n - 1, b => // tail
then (a + b) // tail
))
}
const fibonacci = n =>
{ return helper (n, x => x) // tail
}
console .log (fibonacci (10)) // 55
Некоторые языки позволяют указывать аргументы по умолчанию, поэтому нет необходимости использовать отдельную вспомогательную функцию -
const identity = x =>
x
const fibonacci = (n, then = identity) =>
{ if (n < 2)
return then (n) // tail
else
return fibonacci (n - 2, a => // tail
fibonacci (n - 1, b => // tail
then (a + b) // tail
))
}
console .log (fibonacci (10))
// 55
fibonacci (10, res => console .log ("result is", res))
// result is: 55
Хвост рекурсивный или нет, fibonacci выше - это экспоненциальный процесс, который делает его очень медленным даже при небольших значениях n. линейный процесс стал возможным благодаря представлению состояния нашего вычисления с использованием дополнительных параметров a и b -
const fibonacci = (n, a = 0, b = 1) =>
n === 0
? a // tail
: fibonacci (n - 1, b, a + b) // tail
console .log
( fibonacci (10) // 55
, fibonacci (20) // 6765
, fibonacci (100) // 354224848179262000000
)
Иногда вам нужно будет использовать дополнительные параметры состояния, иногда вам нужно будет использовать вспомогательные функции или продолжения, такие как then.
Мы могли бывозможно, напишите более конкретный ответ, если вы зададите нам конкретную проблему, используя определенный язык.
В ваш отредактированный вопрос вы включили программу Scheme, которая может умножить вложенный список чисел.Сначала мы показываем метод then
(define (deep-mult xs (then identity))
(cond ((null? xs)
(then 1))
((list? (car xs))
(deep-mult (car xs) ;; tail
(λ (a)
(deep-mult (cdr xs) ;; tail
(λ (b)
(then (* a b)))))))
(else
(deep-mult (cdr xs) ;; tail
(λ (a)
(then (* a (car xs))))))))
(deep-mult '((2) (3 (4) 5))) ;; 120
Вы можете использовать параметр состояния acc, как мы это делали и во втором методе, но поскольку входные данные могут быть вложенными, мы должны использовать thenтехника сглаживания потенциальных двух вызовов deep-mult -
(define (deep-mult xs (acc 1) (then identity))
(cond ((null? xs)
(then acc)) ;; tail
((list? (car xs))
(deep-mult (car xs) ;; tail
acc
(λ (result)
(deep-mult (cdr xs) result then)))) ;; tail
(else
(deep-mult (cdr xs) ;; tail
acc
(λ (result) then (* result (car xs)))))))
(deep-mult '((2) (3 (4) 5)))
;; 120
Мне не нравится эта версия программы, потому что каждая техника решает только половину проблемы, тогда какдо этого использовалась только одна техника.
Возможно, разумным решением этой конкретной проблемы является использование append в случае вложенного списка
(define (deep-mult xs (acc 1))
(cond ((null? xs)
acc)
((list? (car xs))
(deep-mult (append (car xs) ;; tail
(cdr xs))
acc))
(else
(deep-mult (cdr xs) ;; tail
(* acc (car xs))))))
(deep-mult '((2) (3 (4) 5)))
;; 120
Однако, append - это дорогостоящая операция со списками, и эта процедура может иметь плохую производительность для списков, которые вложены очень глубоко.Конечно, есть и другие решения.Посмотрите, что вы можете придумать и задать дополнительные вопросы.Я поделюсь решением, которое, как мне кажется, даст больше преимуществ и меньше недостатков.