Elixirのtail call（末尾再帰）を確認する

書籍版の Programming Elixir を読み返していると、P.170 に下記のような末尾再帰の話がありました。

If the very last thing a function does is call itself, there's no need to make the call. Instead, the runtime can simply jump back to their start of the function. If the recursive call has arguments, then these replace the original parameters as the loop occurs

実際その通りなのか、またどれぐらいでスタックが溢れるのか（どれぐらいまでなら、スタックを気にせず再帰させられるのか）を知るため、実際に再帰処理をしてみて確認してみました。

ソースコード

スタック消費版

stack.exs

defmodule Recursion do
  def sub(i) do
    IO.puts i
    0 + sub(i+1)
  end
end

Recursion.sub(0)

末尾再帰版

tailcall.exs

defmodule Recursion do
  def sub(i) do
    IO.puts i
    sub(i+1)
  end
end

Recursion.sub(0)

実行結果

約１時間動かしてみた後のメモリ使用量です。末尾再帰版は、最初から最後まで、ほとんど変動ありませんでした。

スタック消費版	末尾再帰版
2.1GB	30MB

この時の呼び出し回数はスタック消費版は約1億4000万回、末尾再帰版は3億強です。スタック消費版を回数で単純に割ると、5000万回以上の呼び出ししで1GBしか消費しません。

貧乏臭さが抜けないというか、何となく「スタックやヒープを無駄に消費する」のは避けたくなりますが、これだけ繰り返すことができ、その消費量もそう多くないのであれば、末尾再帰になっているかどうかを心配する必要はあまり無いかもしれません（もちろんやることや、状況次第ですが）。

ちなみに ulimit -s が 10240 の環境で、C言語で再帰処理をして見た所、約392,786回で Segmentation fault (core dumped) で落ちました。

# include <stdio.h>

void recursive(unsigned long i)
{
  printf("%ld\n", ++i);
  recursive(i);
}


void main()
{
  recursive(0);
}