再帰を使う時には Task を使おう

まず普通に再帰関数を書きます。

using System;

namespace ConsoleApp1
{
	class Program
	{
		static void Main()
		{
			Console.WriteLine(Recurse(0));
		}

		static int Recurse(int n)
		{
			if (n >= 100_000) return n;
			return Recurse(n + 1);
		}
	}
}

n が 100000 以上になるまで +1 し続ける関数です。しかし結果はこうなります。

Stack overflow.

Recurse メソッドが終了する前に次の Recurse メソッドを再帰呼び出しするため、引数などが解放される前にスタックに積まれていきます。その結果、必要なスタックがあらかじめ割り当てられたサイズを超えてしまい、このエラーが発生します。

これを Task を用いて書き直すと次のようになります。

using System;
using System.Threading.Tasks;

namespace ConsoleApp1
{
	class Program
	{
		static void Main()
		{
			//Console.WriteLine(Recurse(0));
			Console.WriteLine(Recurse(0).Result);
		}

		//static int Recurse(int n)
		//{
		//	if (n >= 100_000) return n;
		//	return Recurse(n + 1);
		//}

		static Task<int> Recurse(int n)
		{
			if (n >= 100_000) return Task.FromResult(n);
			return Task.Run(() => Recurse(n + 1));
		}
	}
}

結果は次のように正常に終了します。

100000

メソッド Recurse は呼び出した Recurse の終了を待ちません。そのため引数などは逐次解放されます。返された Task は合成され、Result プロパティで戻り値を取得できます。

執筆日: 2020/07/25