Есть ли проблемы, которые не могут быть записаны с помощью хвостовой рекурсии?

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

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

Вот пример функции, которая является «рекурсивной» (на самом деле Это' Мы можем создать хвостовую рекурсивную версию, поместив произведение в параметр накопления:

factorial n = f n 1
   where f n product = if n == 0 then product else f (n-1) (n * product)

Внутренняя функция f является хвостовой рекурсивной и компилируется в жесткий цикл.

Я нахожу следующие отличия полезно:

• В итеративной или рекурсивной программе вы решаете задачу размера n с помощью первое решение одной подзадачи размера n-1 . Вычисление факториальной функции попадает в эту категорию, и это может быть выполнено либо итеративно, либо рекурсивно. (Эта идея обобщается, например, на функцию Фибоначчи, где вам нужны оба n-1 и n-2 для решения n .)

• В рекурсивной программе вы решаете задачу размера n путем первого решения двух subproblems of size n/2. Or, more generally, you solve a problem of size n by first solving a subproblem of size k and one of size n-k, where 1 < k < n. Quicksort and mergesort are two examples of this kind of problem, which can easily be programmed recursively, but is not so easy to program iteratively or using only tail recursion. (You essentially have to simulate recursion using an explicit stack.)

• In dynamic programming, you solve a problem of size n by first solving all subproblems of all sizes k, where k. Finding the shortest route from one point to another on the London Underground is an example of this kind of problem. (The London Underground is a multiply-connected graph, and you solve the problem by first finding all points for which the shortest path is 1 stop, then for which the shortest path is 2 stops, etc etc.)