Scalaの末尾再帰除去を確認する

Scalaの末尾再帰除去を実際にjadを使って確かめただけの簡単な記録。 jadの導入は以下のとおり。

brew tap homebrew/binary
brew install jad

簡単な階乗関数で確認すればわかりやすい

object Math {
 
  def fact(n: Int): Int = 
  if (n < 2) 1 
  else n * fact(n - 1) 
 
  def fact2(n: Int): Int = {
    def go(n: Int, acc: Int): Int = {
        if (n < 2) acc
        else go(n -1, n * acc)
    }
    go(n, 1)
  }
 
}

こんなのをコンパイルして jad でどうなっているか確認します。以下その結果。

// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   Math.scala
 
 
public final class Math$
{
 
    public int fact(int n)
    {
        return n >= 2 ? n * fact(n - 1) : 1;
    }
 
    public int fact2(int n)
    {
        return go$1(n, 1);
    }
 
    private final int go$1(int n, int acc)
    {
        do
        {
            if(n < 2)
                return acc;
            acc = n * acc;
            n = n - 1;
        } while(true);
    }
 
    private Math$()
    {
    }
 
    public static final Math$ MODULE$ = this;
 
    static 
    {
        new Math$();
    }
}

factはそのまんま、fact2はちゃんと末尾再帰除去されている様子が見て取れます

Javaではどうなのか

Javaで同じことをしてみる

public class Math {
 
    public int fact(int n) {
        if (n < 2) return n;
        else return n * fact(n - 1);
    }
 
    public int fact2(int n) {
        return go(n, 1);
    }
 
    private int go(int n, int acc) {
        if (n < 2) return acc;
        else return go(n - 1, n * acc);
    }
 
}

こいつは以下のような残念な結果に

// Decompiled by Jad v1.5.8g. Copyright 2001 Pavel Kouznetsov.
// Jad home page: http://www.kpdus.com/jad.html
// Decompiler options: packimports(3) 
// Source File Name:   Math.java
 
 
public class Math
{
 
    public Math()
    {
    }
 
    public int fact(int i)
    {
        if(i < 2)
            return i;
        else
            return i * fact(i - 1);
    }
 
    public int fact2(int i)
    {
        return go(i, 1);
    }
 
    private int go(int i, int j)
    {
        if(i < 2)
            return j;
        else
            return go(i - 1, i * j);
    }
}

こいつをどうするかについては次のURLが詳しい

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です