Perlって末尾再帰の最適化ってやってるの?

30分プログラム、その549。Perlって末尾再帰の最適化ってやっているかを調べようとしてみた。

結論としては、よく分からない。普通の再帰もなかなかスタックオーバーフローで落ちないし、使用しているメモリ量で比較しようとしたけど、メモリ量を取得するうまい方法が見つからない。Devel::Sizeとかは変数の使用メモリ量だし。

とりあえず、末尾再帰だろうと、なかろうと

Deep recursion on subroutine "main::fact" at tail-rec.pl line 25.

という警告がでるので、最適化はしてないんだろう、たぶん。

goto &NAMEなる謎の演算子を使ってやれば、手動で最適化できる。すくなくとも上記の警告はでない。

sub fact_goto($$){
    my ($i,$n) = @_;
    if($n == 0){
	return $i;
    }else{
	@_ = ($i*$n,$n-1);
	goto &fact_goto;
    }
}

ソースコード

#! /usr/bin/perl
# -*- mode:perl; coding:utf-8 -*-
#
# tail-rec.pl -
#
# Copyright(C) 2009 by mzp
# Author: MIZUNO Hiroki / mzpppp at gmail dot com
# http://howdyworld.org
#
# Timestamp: 2009/03/20 22:23:32
#
# This program is free software; you can redistribute it and/or
# modify it under MIT Lincence.
#

use strict;
use warnings;
use Devel::StackTrace;

sub fact($){
    my ($n) = @_;
    if($n == 0){
	1;
    }else{
	$n * &fact($n-1);
    }
}

sub fact_iter($$){
    my ($i,$n) = @_;
    if($n == 0){
	return $i;
    }else{
	&fact_iter($i*$n,$n-1,);
    }
}

sub fact_goto($$){
    my ($i,$n) = @_;
    if($n == 0){
	return $i;
    }else{
	@_ = ($i*$n,$n-1);
	goto &fact_goto;
    }
}

fact(100);
fact_iter(1,100);
fact_goto(1,100);

参考

• 過去の30分プログラム