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?
Because I can not replace this:
(recur (dec line) colum
(pascal (dec line) (dec colum), acc))))
To this:
(recur (dec line) colum
(recur (dec line) (dec colum), acc))))
Best Regards
Maybe my answer is unrelated to an recursion, and this question at all unlike the answer by @Sylwester, but it's still useful to show an another way to solve this problem.
Assuming that pascal triangle has this properties:
Any other elements can be solved by formula:
Than means, that You can solve any elements of pascal triangle by linear algorithm with time complexity O(n^3). It may be not much cool than recursive version with O(n^2) and recursion, but it doesn't blow stack and it use combinatorics, which is in my opinion even better, because it's simpler and safer version. So, here we go:
As You can see there is used
naive-factorial
function, which takesn
multiplication, which lead us to O(n^3). It's the same as your function, but without any recursion.For pascal triangle there is also much than one way to solve them in different ways. Some of them are very tricky, take a look, if you have much time: rosettacode.org
Also in you version your use
int
math in clojure by+
, please use in+'
function in any cases which can lead to large numbers(assuming that that means that the addition will be lead to converting your values to biginteger type, which allows very large numbers).Also I translated the scheme version introduced by @Sylwester to a clojure:
It's maybe can be improved, but shows the idea. It's calculated the entire triangle from third line to previous one of provided input and then gets the answer. Pretty awesome and pure magic of function approach.
The performance of this version is much more worse, than the linear version. So it gets:
But it's still much cleaner and cooler ;)
Only half of your calls are by tail recursion so the other half can blow the stack. Compare it with this:
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!