再帰とループの速度を比較してみた

はじめに

最近再帰を覚えたのですが、繰り返し処理を実装するときにループと再帰をどう使い分けたら良いのか疑問に思いました。
調べると可読性によって書き分けたりするなど出てくるのですが、メモリ効率ではどうなのか気になったので実際に書き比べてみました。

自分の書ける言語がSwift, Java, C#だけなのでこの３つで測定した結果とコードを載せています。
内容としては１〜nまでの総和を求める関数を、forループ、末尾再帰、ヘッド再帰の３通りで書き分けて、それぞれの処理時間を出力するようにしました。

末尾再帰は再帰呼び出しのみを関数の戻り値とするもので、末尾呼び出し最適化とも呼ばれているようです。
こちらはヘッド再帰（末尾再帰以外の再帰）に対してコールスタックが積み上げられることがないので、スタックオーバーフローを回避できるメリットがあります。

実行環境

macOS 11.6 (Apple M1, 16GB)

Swift

• Xcode12.5.1
• Swift 5.4.2

Java

• openjdk 11.0.10

Windows 10 Pro (Intel Core m3-7Y30 1ghz, 4GB)

C♯

• Visual Studio 15.9.14
• C# 7.0

結果

＊単位は全て秒です
loop:　ループ
tail:　末尾再帰
head:　ヘッド再帰

Swift

loop: 0.1533259153366089
tail: 0.024509072303771973
head: 0.02441096305847168

Java

loop: 0.000065084
tail: 0.000343166
head: 0.000244625

C#

loop: 0.0002692
tail: 0.0029946
head: 0.0008169

ミリ秒以下の差だったりもしますが、書き方によって何倍も速度が異なる結果になりました。
Swiftでは再帰の方がループよりも早いですが、他２つではその逆であったりと言語による違いも出ました。

コード

Swift

import UIKit

func loop(n: Int) -> Int{
    var sum: Int = 0;
    for i in 1...n {
        sum += i;
    }
    return sum;
}


func tailRecursion(n: Int, sum: Int) -> Int {
    if(n < 1){
        return sum;
    }
    return tailRecursion(n: n - 1, sum: sum + n)
}


func headRecursion(n: Int) -> Int{
    if(n < 1){
        return n;
    }
    return n + headRecursion(n: n - 1)
}



let startRooop = Date()
loop(n: 10000)
let endRoop = Date()
print("loop: \(endRoop.timeIntervalSince(startRooop))")

let startRec = Date()
tailRecursion(n: 10000, sum: 0)
let endRec = Date()
print("tail: \(endRec.timeIntervalSince(startRec))")

let startHead = Date()
headRecursion(n: 10000)
let endHead = Date()
print("head: \(endHead.timeIntervalSince(startHead))")

Java

import java.math.*;

public class Loop{

  public static int loop(int n){
    int sum = 0;
    for(int i = 0; i <= n; i++){
      sum += i;
    }

    return sum;
  }

public static int tailRecursion(int n, int sum){
  if(n < 1){
    return sum;
  }

  return tailRecursion(n - 1, sum + n);
}

public static int headRecursion(int n){
  if(n < 1){
    return n;
  }

  return n + headRecursion(n - 1);
}

public static String toSeconds(long elapsed){
  double sec = (double) elapsed / 1000_000_000;
  return BigDecimal.valueOf(sec).toPlainString();
}

public static void main(String[] args){

  long startLoop = System.nanoTime();
  int n = loop(10000);
  long endLoop = System.nanoTime();
  System.out.println("loop: " + toSeconds (endLoop - startLoop));

  long startTail = System.nanoTime();
  int tail = tailRecursion(10000, 0);
  long endTail = System.nanoTime();
  System.out.println("tail: " + toSeconds(endTail - startTail));

  long startHead = System.nanoTime();
  int head = headRecursion(10000);
  long endHead = System.nanoTime();
  System.out.println("head: " + toSeconds(endHead - startHead));

}
}

C#

class Program
    {

        public static int loop(int n)
        {
            int sum = 0;
            for(int i = 0; i <= n; i++)
            {
                sum += i;
            }

            return sum;
        }

        public static int tail(int n, int sum)
        {
            if(n < 1)
            {
                return sum;
            }

            return tail(n - 1, sum + n);
        }

        public static int head(int n)
        {
            if(n < 1)
            {
                return n;
            }

            return n + head(n - 1);
        }

        public static double toSeconds(Stopwatch sw)
        {
            double ms = sw.Elapsed.TotalMilliseconds;
            return  ms / 1000;
        }

        static void Main(string[] args)
        {

            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            loop(10000);
            sw.Stop();
            Console.WriteLine($"loop: {toSeconds(sw)}");

            var swTail = new System.Diagnostics.Stopwatch();
            swTail.Start();
            tail(10000, 0);
            swTail.Stop();
            Console.WriteLine($"tail: {toSeconds(swTail)}");

            var swHead = new System.Diagnostics.Stopwatch();
            swHead.Start();
            head(10000);
            swHead.Stop();
            Console.WriteLine($"head: {toSeconds(swHead)}");

            MessageBox.Show("end");
        }
    }

おわりに

今回の計測で、再帰によって処理速度が改善される可能性があることがわかりました。
特に大きなデータを扱うプログラムでは、こうした違いを意識することがパフォーマンスに大きく影響するのではと思います。

今回の記事について不正確な情報や指摘がありましたらいただけると嬉しいです。