algorithm - Perl 在计算阶乘 N 的递归实现中保留中间结果的位置？

Question

Perl 上有一个计算阶乘 N 的递归实现。

sub fact {
  my ($n) = shift;
  return $n if $n <= 2;
  return $n * fact($n - 1);
}

有人可以解释一下 Perl 在函数给出结果之前在哪里保存中间结果吗？

UPD以及我如何通过使用调试器或使用其他东西来查看它们？

从答案中我被解释说这个值保存在一个堆栈中，但是我如何从堆栈中看到这些值？

Answer 1

通过递归，每次调用中传递的任何参数都将进入调用帧/堆栈。通过使用 Carp & cluck，您可以看到调用帧。中间结果是在堆栈在达到基本情况（$v == 1）时展开时计算的。它只能在CPU寄存器中吗？运算符 (*) 将此中间结果与堆栈上的 $v 相乘。另请查看这篇文章。

#!/usr/bin/env  perl

use strict;
use IO::Handle;
use Carp qw(cluck);

STDOUT->autoflush(1);
STDERR->autoflush(1);

sub factorial {
    my $v = shift;

    dummy_func();
    return 1 if $v == 1;
    print "Variable v value: $v and it's address:", \$v, "\ncurrent sub factorial addr:", \&factorial, "\n","-"x40;
    return $v * factorial($v - 1);
}

sub dummy_func {
    cluck;
}

factorial(5);

在调试模式下运行也会有所帮助。

perl -d 阶乘.pl

Answer 2

返回的标量$n存储在堆栈中。

这是调用之前堆栈的样子fact：

• $n递归级别 0 中返回的标量
• 列表：
  • $n递归级别 1 中返回的标量
  • 列表：
    • $n递归级别 2 中返回的标量
    • 列表：
      • $n-1递归级别 2 中返回的标量
      • \&fact递归级别 2 中返回的标量

这是调用后堆栈的样子fact：

• $n递归级别 0 中返回的标量
• 列表：
  • $n递归级别 1 中返回的标量
  • 列表：
    • $n递归级别 2 中返回的标量
    • fact($n - 1)递归级别 2 中返回的标量

此时，乘法运算符会将堆栈中的最后两个值相乘，并将结果放入堆栈。

• $n递归级别 0 中返回的标量
• 列表：
  • $n递归级别 1 中返回的标量
  • 列表：
    • $n * fact($n - 1)递归级别 2 中返回的标量

然后子返回，

• $n递归级别 0 中返回的标量
• 列表：
  • $n递归级别 1 中返回的标量
  • fact($n - 1)递归级别 1 中返回的标量

等等。

Answer 3

Intermediate results of any call are kept on the stack, just like local variables within a function.

return $n * fact($n - 1);

is processed equivalently to:

my $temp = fact($n - 1);
return $n * $temp;

UPDATE: I see you're also interested in where the product is held before returning it. That's also in a temporary on the stack, so it's equivalent to:

my $temp1 = fact($n - 1);
my $temp2 = $n * $temp1;
return $temp2;

Answer 4

由于$n被声明为my $n，它是一个词法范围的变量，并且存储在堆栈中而不是系统表中。有关更多信息，请参阅通过 my() 的 Perl 变量。