tail call optimization for tail recursive lambda function
I am trying to write recursive anonymous function, so far what works for me is to use the Y combinator.
%{ Call lambda function with any number of arguments. %}
call_ = @feval;
%{ Internal subroutine for function IF_. %}
if__ = @(varargin) varargin{3 - varargin{1}}();
%{ If predicate PRED is true, evaluate thunk IF_CLAUSE. %}
% { Otherwise, evaluate thunk ELSE_CLAUSE. %}
if_ = @(pred, if_clause, else_clause) if__(pred, if_clause, else_clause);
%{ Determine if X is a cell array. %}
is_cell_ = @(x) isa(x, 'cell');
%{ Call function FUNC with elements in argument list ARG_LS as arguments. %}
apply_ = @(func, arg_ls) if_(is_cell_(arg_ls), ...
@() func(arg_ls{:}), ...
@() func(arg_ls(:)));
%{ Compute a fixed point for the function H. %}
Y_ = @(h) call_(@(x) x(x), @(g) h(@(varargin) apply_(g(g), varargin)));
So, for example, to define factorial, we can use the Y combinator:
make_fact__ = @(f) @(n, accum) if_(n == 0, @() accum, @() f(n - 1, n * accum))
fact__ = Y_(make_fact__)
fact_ = @(n) fact__(n, 1)
fact_(5)
Note the factorial defined above is tail recursive. Is there anyway to optimize the tail call, so that the tail recursive function won't blow the stack for large N?
Searching the internet gives me the equivalent question in Python (Does Python optimize tail recursion?), but I can't really make it work in Octave/Matlab, using only anonymous function.
I have also found some articles about trampoline, again I find it difficult to implement try-catch using only anonymous function, which is needed in the implementation of trampoline.
Thanks!
链接地址: http://www.djcxy.com/p/80548.html上一篇: F＃创建没有递归，库函数或循环的因子函数