我正在尝试编写一个 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)))
原因是试图弄清楚迭代多项式的行为方式 - 类似于 Robert May 总体方程,但多项式不同。
无论如何,我对 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)) ));
Maxima 接受这一点。现在作为一个简单的示例函数来迭代...
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
/code> 函数将被输入两次以上 - 这似乎非常极端,因为耗尽了堆栈。
当然,一旦我有了基本的想法,我可能会将特殊情况 n=1
作为有效的另一个基本情况以提高效率(不太困惑的结果函数定义)并添加更多检查,但是我现在只想要一些在微不足道的情况下不会溢出的东西。
我误解了什么?
最佳答案
这就是我的想法。有必要替换到 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
时,那就是一个问题。
无论如何,我希望这个解决方案在某种程度上对您有用。
关于recursion - 函数的递归迭代导致堆栈溢出,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/68726208/