时间戳

首页 > 解决方案 > 获取堆栈溢出的函数的递归迭代

recursion - 获取堆栈溢出的函数的递归迭代

问题描述

我正在尝试编写一个 Maxima 函数来迭代作为参数提供的另一个函数。目标基本上是...

iter(f,0) ........ gives the identity function lambda([x],x)
iter(f,1) ........ gives f
iter(f,2) ........ gives lambda([x],f(f(x))
iter(f,3) ........ gives lambda([x],f(f(f(x)))

原因是试图弄清楚迭代多项式的行为方式 - 类似于罗伯特梅人口方程，但多项式不同。

无论如何，我对 Maxima 很陌生（至少对于那些看起来更像是简单编程而不仅仅是寻求解决方案的事情）并且经过一段时间试图找出我做错了什么之后，我想我已经消除了所有愚蠢的事情错误，我必须对 Maxima 的工作方式有更根本的误解。

我有的...

iter(f,n) := if is (n=0)
  then lambda ([x], x)
  else block ([n2: floor (n/2),
               nr: is (n2*2#n),
               ff: iter (f,n2) ], if nr then lambda ([x],f(ff(ff(x))))
                                        else lambda ([x],  ff(ff(x)) ));

千里马接受了这一点。现在作为一个简单的示例函数来迭代......

inc(x):=x+1;

还有一些测试 - 首先是基本情况......

iter(inc,0);

那行得通-它lambda([x],x)按预期提供。接下来，“迭代”一次……

iter(inc,1);

我期待与 等价的东西inc，但由于它的编写方式，更像是lambda([x],inc(identity(identity(x)))但更混乱。我实际上得到的是堆栈溢出......

Maxima encountered a Lisp error:
Control stack exhausted (no more space for function call frames).
This is probably due to heavily nested or infinitely recursive function
calls, or a tail call that SBCL cannot or has not optimized away.
...

我不明白为什么is (n=0)基本情况检查无法在递归调用中发现它，所以我不明白为什么这个iter函数会被输入两次以上n=1- 耗尽堆栈似乎非常极端。

当然，一旦我有了基本的想法，我可能会将特殊情况n=1作为有效的另一个基本情况来提高效率（一个不那么混乱的结果函数定义）并添加更多检查，但我只想要一些不会堆栈溢出的东西现在的情况。

我有什么误解？

标签： recursionmaxima

解决方案

这就是我想出的。有必要替换到身体中，lambda因为身体没有被评估——我想你已经遇到了这个重要的一点。

(%i3) iter(f, n) := if n = 0 then identity elseif n = 1 then f
            else subst([ff = iter(f, n - 1),'f = f],
                       lambda([x], f(ff(x)))) $
(%i4) iter(inc, 0);
(%o4)                       identity
(%i5) iter(inc, 1);
(%o5)                          inc
(%i6) iter(inc, 2);
(%o6)               lambda([x], inc(inc(x)))
(%i7) iter(inc, 3);
(%o7)             lambda([x], inc(inc(inc(x))))
(%i8) iter(inc, 4);
(%o8)          lambda([x], inc(inc(inc(inc(x)))))
(%i9) inc(u) := u + 1 $
(%i10) iter(inc, 4);
(%o10)               lambda([x], inc(x + 3))
(%i11) %(10);
(%o11)                         14
(%i12) makelist (iter(cos, k), k, 0, 10);
(%o12) [identity, cos, lambda([x], cos(cos(x))), 
lambda([x], cos(cos(cos(x)))), lambda([x], 
cos(cos(cos(cos(x))))), lambda([x], cos(cos(cos(cos(cos(x)))))), 
lambda([x], cos(cos(cos(cos(cos(cos(x))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(x)))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(cos(x))))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(cos(cos(x)))))))))), 
lambda([x], cos(cos(cos(cos(cos(cos(cos(cos(cos(cos(x)))))))))))]
(%i13) map (lambda([f], f(0.1)), %);
(%o13) [0.1, 0.9950041652780257, 0.5444993958277886, 
0.8553867058793604, 0.6559266636704799, 0.7924831019448093, 
0.7020792679906703, 0.7635010336918854, 0.7224196362389732, 
0.7502080588752906, 0.731547032044224]

Maxima 几乎擅长这样的事情——因为它建立在 Lisp 之上，所以存在正确的概念元素。但是，在处理此类问题时，缺少词法范围是一个严重的问题，因为这意味着当您f在函数定义中引用时，它与f可能存在于它之外的相同。当解决方案取决于仔细区分f您的意思时，这就是一个问题。

无论如何，我希望这个解决方案在某种程度上对你有用。

推荐阅读