3. ループと再帰

著者:梅谷武

各言語において繰り返し処理をループで書いた場合と再帰で書いた場合とを比較する。

作成:2024-05-12
更新:2024-09-02

3.1 言語仕様

C++

C++には繰り返し構文として次の三つがある。

for文
while文
do-while文

OCaml

OCamlには繰り返し構文として次の二つがある。

for文
while文

これとは別にリストの要素に関する繰り返しのためのリストイテレーターがある。

List.iter
List.map
List.filter
List.fold_right
List.fold_left

OCamlのループと再帰についてはLoops and Recursionsを参照のこと。

Racket

Racketには繰り返しのための関数として次の二つがある。

forには様々なバリエーションがあり、これにrangeのバリエーションを組み合わせると多彩な繰り返し処理を記述することができる。これとは別にラベル付きletを使ってループ形式で末尾再帰最適化される処理を記述することができる。

Racketの繰り返しについての概説はThe Racket Guide＞11 Iterations and Comprehensions、詳細仕様はThe Racket Reference＞3 Syntactic Forms＞3.18 Iterations and Comprehensionsにある。

3.2 for文

本節では各言語のfor文を比較してみる。前章と同じ課題を用いる。

課題

自然数nを与えたとき1からnまでの総和

n
∑
k=1

を求める関数sum3(n)をfor文で実装する。

C++

sum3.cpp:

#include <print>
#include <stdexcept>
#include <string>
 
long sum_for(long n) {
  long acc = 1l;
  for (long i = 2l; i <= n; ++i)
    acc += i;
  return acc;
}
 
int main(int argc, char* argv[]) {
  try {
    if (argc != 2) {
      throw std::invalid_argument(
        "Usage: sum3 <non-negative integer>");
    }
    long n = std::stol(argv[1]);
    if (n < 0l) {
      throw std::invalid_argument(
        "The argument must be a non-negative integer.");
    }
    long result = sum_for(n);
    std::println("sum({}) = {}", n, result);
  } catch (const std::logic_error& e) {
    std::println(stderr, "Logic error: {}", e.what());
  } catch (const std::runtime_error& e) {
    std::println(stderr, "Runtime error: {}", e.what());
  } catch (const std::exception& e) {
    std::println(stderr, "Another std::exception: {}", e.what());
  } catch (...) {
    std::println(stderr, "Unknown exception.");
  }
  return 0;
}

n = 100000000で測定する。

$ g++ -std=c++23 -O2 -o sum3_g sum3.cpp
$ measure ./sum3_g 100000000
sum(100000000) = 5000000050000000
======================================
Process exited with status: 0
total time:  0.063972 [sec]
mem  size:       3716 [KB]
code size:        119 [KB]

$ clang++ -std=c++23 -O2 -o sum3_l sum3.cpp
$ measure ./sum3_l 100000000
sum(100000000) = 5000000050000000
======================================
Process exited with status: 0
total time:  0.001357 [sec]
mem  size:       3616 [KB]
code size:         92 [KB]

末尾再帰版:sum2.cppとほぼ同じ傾向。

OCaml

sum3.ml:

open Printf
 
let sum_for n =
  let acc = ref 1 in
  for i = 2 to n do
    acc := !acc + i
  done;
  !acc
 
let () =
  try
    if Array.length Sys.argv <> 2 then
      raise (Invalid_argument
        "Usage: sum3 <non-negative integer>")
    else
      let n = int_of_string Sys.argv.(1) in
      if n < 0 then
        raise (Invalid_argument
          "The argument must be a non-negative integer.")
      else
        let result = sum_for n in
        printf "sum(%d) = %d\n" n result
  with
    | Invalid_argument msg ->
        eprintf "Logic error: %s\n" msg
    | Failure msg ->
        eprintf "Runtime error: %s\n" msg
    | exn ->
        eprintf "Another exception: %s\n" (Printexc.to_string exn)

n = 100000000で測定する。

$ ocamlopt -O2 -o sum3 sum3.ml
$ measure ./sum3 100000000
sum(100000000) = 5000000050000000
======================================
Process exited with status: 0
total time:  0.122344 [sec]
mem  size:       2892 [KB]
code size:       1111 [KB]

末尾再帰版:sum2.mlとほぼ同じ。

Racket

ここではforを使ったsum3a.rktとラベル付きletを使ったsum3b.rktを比較する。

sum3a.rkt:

#lang racket
(require iso-printf)
 
(define (sum_for n)
  (define acc 1)
  (for ([i (in-range 2 (+ n 1))])
    (set! acc (+ acc i)))
  acc)
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (cond
    [(not (= (vector-length args) 1))
      (error "Usage: sum3a <non-negative integer>")]
    [else
      (let ([n (string->number (vector-ref args 0))])
        (cond
          [(not (integer? n))
            (error "The argument must be an integer.")]
          [(< n 0)
            (error "The argument must be a non-negative integer.")]
          [else
            (let ([result (sum_for n)])
              (printf "sum(%d) = %d\n" n result))]))])))
 
(main (current-command-line-arguments))

sum3b.rkt:

#lang racket
(require iso-printf)
 
(define (sum_let n)
  (cond
    [(= n 0) 0]
    [(= n 1) 1]
    [else
      (let loop ([acc 1] [i 2])
        (if (= i n) (+ acc i)
          (loop (+ acc i) (+ i 1))))]))
 
(define (main args)
  (with-handlers
    ([exn:fail? (λ (e) (eprintf "%s\n" (exn-message e)))]
     [exn? (λ (e) (eprintf "Unexpected: %s\n" (exn-message e)))])
  (cond
    [(not (= (vector-length args) 1))
      (error "Usage: sum3b <non-negative integer>")]
    [else
      (let ([n (string->number (vector-ref args 0))])
        (cond
          [(not (integer? n))
            (error "The argument must be an integer.")]
          [(< n 0)
            (error "The argument must be a non-negative integer.")]
          [else
            (let ([result (sum_let n)])
              (printf "sum(%d) = %d\n" n result))]))])))
 
(main (current-command-line-arguments))

n = 100000000で測定する。

$ raco exe sum3a.rkt
$ measure ./sum3a 100000000
sum(100000000) = 5000000050000000
======================================
Process exited with status: 0
total time:  0.757148 [sec]
mem  size:     134068 [KB]
code size:      12443 [KB]

$ raco exe sum3b.rkt
$ measure ./sum3b 100000000
sum(100000000) = 5000000050000000
======================================
Process exited with status: 0
total time:  0.682071 [sec]
mem  size:     133820 [KB]
code size:      12443 [KB]

末尾再帰版:sum2.rktとラベル付きlet版:sum3b.rktはほぼ同じ、for版:sum3a.rktはやや遅い。

3.3 まとめ

C++とOCamlについては末尾再帰とforループはほぼ同等、Racketについては末尾再帰とラベル付きletはほぼ同等、forループはやや遅い。

This document is licensed under the MIT License.
Copyright (C) 2024 Takeshi Umetani