Хвостовая рекурсия, вызывающая хвостовую рекурсию

Question

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

(defn pascal [line colum, acc]
  (if (or (= line 0) (= line colum) (= colum 0))
    (+ acc 1)
    (recur (dec line) colum
           (pascal (dec line) (dec colum), acc))))

У меня такой вопрос: поскольку я использую рекурсивный вызов в качестве параметра для моей рекурсии, он все еще действителен?

Потому что я не могу заменить это:

(recur (dec line) colum
       (pascal (dec line) (dec colum), acc))))

К этому:

(recur (dec line) colum
       (recur (dec line) (dec colum), acc))))

С уважением

Answer 1

Только половина ваших вызовов выполняется хвостовой рекурсией, поэтому другая половина может перебить стек. Сравните это с этим:

(defn factorial (n) 
  (if (= n 1)
      1
      (* n (factorial (n - 1)))))

Вот (factorial (n - 1)) нужно закончить перед продолжением (* n <result>) который является стековым фреймом, ожидающим пока выполняется рекурсия.

Это лучше, чем то, что вы делаете, но гораздо лучше, если все так и есть!

Answer 2

Возможно, мой ответ не связан с рекурсией, и этот вопрос совсем не похож на ответ @Sylwester, но все же полезно показать другой способ решения этой проблемы.

Предполагая, что этот треугольник имеет следующие свойства:

1. Первый и последний пункт в каждой строке паскаль треугольника '1'
2. Второй и предпоследний номер строки

3. Любые другие элементы могут быть решены по формуле:

   

Это означает, что Вы можете решать любые элементы треугольника Паскаля по линейному алгоритму с временной сложностью O(n^3). Это может быть не очень круто, чем рекурсивная версия с O(n^2) и рекурсией, но она не разрушает стек и использует комбинаторику, что, на мой взгляд, даже лучше, потому что это более простая и безопасная версия. Итак, поехали:

(defn naive-factorial[n]
  (reduce *' (range 1 (inc n))))

(defn combinatoric-formula[line pos]
  (if (<= pos line)
    (/ 
     (naive-factorial line) 
     (*' (naive-factorial pos) 
         (naive-factorial (- line pos))))))

Как видите, там используется naive-factorial функция, которая принимает n умножение, которое приводит нас к O(n^3). Это то же самое, что и ваша функция, но без какой-либо рекурсии.

Для Паскаля треугольника также есть много способов решить их по-разному. Некоторые из них очень хитрые, посмотрите, если у вас много времени: rosettacode.org

Также в вашей версии ваше использование int математика в ближайшем будущем + пожалуйста, используйте в +' работать в любых случаях, которые могут привести к большим числам (при условии, что это означает, что сложение приведет к преобразованию ваших значений в тип biginteger, который допускает очень большие числа).

Кроме того, я перевел версию схемы, представленную @Sylwester, на рассмотрение:

(defn pascal [row col]
  (let [aux  
        (fn aux [tr tc prev acc]
          (cond (> tr row) (throw (.Exception "invalid input"))         
                (and (= col tc) (= row tr)) (+' (first prev) (second prev)); the next number is the answer
                (= tc tr) (recur (+' tr 1) 1 (cons 1 acc) '(1))                  ; new row 
                :else (recur tr               ; new column
                           (+' tc 1) 
                           (next prev)
                           (cons (+' (first prev) (second prev)) acc))))]
    (if (or (zero? col) (= col row))
      1
      (aux 2 1 '(1 1) '(1)))))

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

Производительность этой версии намного хуже, чем у линейной версии. Так и получается:

(time (combinatoric-formula 1000 100))
"Elapsed time: 2.73794 msecs" for linear version

(time (pascal 1000 100))
"Elapsed time: 135.426888 msecs" for tail recursion version

Но это все еще намного чище и прохладнее;)