尾递归调用尾递归 [英] Tail recursion calling tail recursion

问题描述

我试图用尾递归来解决pascal的三角形。我理解做尾递归，函数调用语句应该是最后一条指令。像这里：

I'm trying to solve the pascal's triangle with tail recursion. I understand to do tail recursion, the function call statement should be the last instruction. Like here:

(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))))

我的问题是：由于我使用递归调用作为递归的参数， ？

My question is: Since I use a recursive call as a parameter for my recursion, is it still valid?

因为我无法替换：

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

到这个：

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

最好的方法

推荐答案

只有一半的呼叫是通过尾递归进行的，所以另一半可以击中堆栈。与此比较：

Only half of your calls are by tail recursion so the other half can blow the stack. Compare it with this:

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

code>（factorial（n-1））需要在继续（* n< result>）堆栈帧在递归运行时等待。

Here (factorial (n - 1)) needs to finish before the continuation (* n <result>) which is a stack frame waiting while the recursion is running.

它不比尾叫都好，但是它更好，如果都是和这是可能的！

It's better than neither being tail calls, but its much better if all are and it is possible!

这篇关于尾递归调用尾递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！