[VRChat] U#で再帰呼出

[RecursiveMethod] ※2022/5/18追記

UdonSharpでは再帰呼出を行う関数には[RecursiveMethod]属性を付ける必要があるようです
参考：https://github.com/MerlinVR/UdonSharp/wiki/UdonSharp#recursivemethod
まだ検証できていませんが、これを付ければこの記事で述べられている問題は発生しなさそうです（ただしパフォーマンスに問題があるとのことなので使いどころには注意）
情報提供して下さった @nyakome306 様に感謝！

TL; DR

末尾再帰以外はやめとけ

やりたかったこと

配列をソートしたかったけど、C#組み込みのソート関数が使えなかったので自分でクイックソートを実装した
…はいいが、なぜかうまく動かなかったので調査

環境

Unity 2019.4.31f1
VRCSDK 2022.02.16.19.13
UdonSharp v0.20.3

検証

ソート関数だと挙動が追いにくいので簡単な再帰関数を作った

        void Start()
        {
            Iter(1);
        }

        private void Iter(int num)
        {
            Debug.Log(num);
            if (num >= 4) { return; }
            Iter(num + 1);
            Iter(num * 2);
        }

このプログラムの想定挙動はこうだ。

• Iter(1)が呼び出される
  • 1+1=2→Iter(2)が呼び出される
    • 2+1=3→Iter(3)が呼び出される
      • 3+1=3→Iter(4)が呼び出されてEarly Return
      • 3*2=6→Iter(6)が呼び出されてEarly Return
    • 2*2=4→Iter(4)が呼び出されてEarly Return
  • 1*2=2→Iter(2)が呼び出される
    • 2+1=3→Iter(3)が呼び出される
      • 3+1=3→Iter(4)が呼び出されてEarly Return
    • 2*2=4→Iter(4)が呼び出されてEarly Return

よって、デバッグログには以下の順で書き出されるべきである。
1 2 3 4 6 4 2 3 4 6 4
しかし現実は非情であった。コンソールには
1 2 3 4 8 16 32
といういかにも2の累乗っぽい数列が現れたのだ。3邪魔
他にもいくつかの値で同様の検証を行い、以下の仮説を立てた。以下、値は上記プログラムのものである。

• Iter(1)が呼び出される num=1
  • 1+1=2→Iter(2)が呼び出される num=2
    • 2+1=3→Iter(3)が呼び出される num=3
      • 3+1=3→Iter(4)が呼び出されてEarly Return num=4
      • 4*2=8→Iter(8)が呼び出されてEarly Return num=8
    • 8*2=16→Iter(16)が呼び出されてEarly Return num=16
  • 16*2=32→Iter(32)が呼び出されてEarly Return num=32

そう、つまり仮引数numに実引数の値が代入されたタイミングで、呼び出し元の関数呼び出しの仮引数も書き換わってしまうのである。これは厄介な問題だ。

問題解決のために試したこと

仮引数が書き換わってしまうなら値渡しで別の変数にコピーしておけばいいじゃない

そう思っている時期がありました、ええ。

        void Start()
        {
            Iter(1);
        }

        private void Iter(int num)
        {
            int _num = num + 0; // +0で確実に値渡しさせようとしている
            Debug.Log(_num);
            if (_num >= 4) { return; }
            Iter(_num + 1);
            Iter(_num * 2);
        }

最初に仮引数numを別の変数_numに値渡しコピーして今後それを使うようにした
結果：
1 2 3 4 8 16 32

…変わっとらんやんけ！！！

仮説：オブジェクト内static？

そんなもの(用語)はない…でも言ってしまったからには…どうする筆者！？

ので説明しよう
これは、「同一オブジェクト内であれば値が必ず同じになる変数」を指す。

Q. 同一オブジェクトなら値は必ず同じ、それはその通りでは？？？
A. フィールド変数ならそれは保証されるべきである。しかし関数内で宣言した一時変数になれば話は別。宣言ごとに違う変数(メモリ領域)を使うべきだ。

今回、仮引数numや関数内定義変数_numは関数内で宣言した一時変数と言える。通常、これらはそれぞれ関数呼び出し時・宣言時にメモリ領域を確保され、関数終了時など適切なタイミングで破棄される。しかし、U#(少なくとも2022/5/12現在のバージョン)では同じインスタンスの同じ変数(一時変数含む)が同じメモリ領域を指してしまうのではないか？この挙動がstaticな変数に似ていることから「オブジェクト内static」な変数と呼ぶことにした。

じゃあどうすればいいの？

• 単純なループに置き換えられないか検討する
• 末尾再帰に置き換える
  • これなら引数が変わろうがその後使うことはないのでOK
• スタックメモリを自分で実装し、引数を使わなくてもよいような運用をする
• 諦めてU#の問題解決を待つ

検証で使ったコードの場合

スタックメモリを実装し、こうすれば一応は動いた

        void Start()
        {
            Iter();
        }

        // 30個というのはテキトーな値なので使う場面によって変える
        private int[] stack = new int[30];
        private int stackpoint = 0;

        private void PushStack(int value)
        {
            stack[stackpoint] = value;
            stackpoint++;
        }
        private int PopStack()
        {
            stackpoint--;
            return stack[stackpoint];
        }

        private void Iter()
        {
            PushStack(1);
            while (stackpoint > 0)
            {
                int num = PopStack();
                Debug.Log(num);
                if (num >= 4) { continue; }
                // 順番が逆になっていることに注意
                PushStack(num * 2);
                PushStack(num + 1);
            }
        }

しかし、これも関数末尾で連続して呼び出していたためにできた荒業であり、一般に使えるものではない。