尾递归调用尾递归
我在试着用尾部递归解pascal三角形。我知道要做尾递归，函数调用语句应该是最后一条指令。如下所示：
(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))))诚挚的问候
回答 2
Stack Overflow用户
发布于 2015-12-16 04:13:34
只有一半的调用是通过尾递归进行的，所以另一半调用可能会打乱堆栈。将其与以下内容进行比较：
(defn factorial (n)
(if (= n 1)
1
(* n (factorial (n - 1)))))在这里，(factorial (n - 1))需要在延续(* n <result>)之前完成，这是一个在递归运行时等待的堆栈帧。
这比两者都不是尾部调用要好，但如果所有都是it is possible!，那就更好了
Stack Overflow用户
发布于 2015-12-16 05:05:04
也许我的答案与递归无关，这个问题与@Sylwester的答案完全不同，但它仍然有助于展示另一种解决此问题的方法。
假设pascal三角形具有以下属性：
pascal三角形每行的第一项和最后一项是'1'
- Second，倒数第二项是行数
- ，任何其他元素都可以用公式求解：
这意味着你可以用线性算法求解pascal三角形的任何元素，时间复杂度为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)。它与您的函数相同，但没有任何递归。
对于pascal三角，也有很多不同的方法来解决它们。其中一些非常棘手，如果你有很多时间，请看一下：rosettacode.org
另外，在您的版本中使用+的clojure中的int数学，请在任何情况下使用+'函数，这可能导致大数字(假设这意味着加法将导致将您的值转换为biginteger类型，这允许非常大的数字)。
此外，我还将@Sylwester引入的方案版本翻译为clo_j_ure：
(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但它仍然更干净，更凉爽;)
https://stackoverflow.com/questions/34297481
复制相似问题
腾讯云开发者
