JavaScript - 関数(階乗を求める)

初めてのJavaScript 第2版
Shelley Powers (著)
武舎 広幸、武舎 るみ (訳)

開発環境

• OS X Lion - Apple(OS)
• Safari (Webプラウザ)
• TextWrangler(Text Editor) (BBEditの無料、light版)
• Script言語:JavaScript
• JavaScript Library: jQuery

『初めてのJavaScript 第2版』(シェリー・パワーズ著(Shelley Powers著)、武舎 広幸+武舎 るみ訳、オライリー・ジャパン、2009年、ISBN978-4-84312-225-5) の5章(JavaScriptの関数)練習問第5-1を解いてみる。

その他参考書籍

• JavaScript 第6版
• JavaScriptリファレンス 第6版
• 『jQueryクックブック』(jQuery Community Experts 著、株式会社クイープ 訳、オライリー・ジャパン、2010年、ISBN978-4-87312-268-2)

5-1.

コード(TextWrangler)

function calcFactorialRecursively(n){
  if(n <= 1) return 1;
  return n * calcFactorialRecursively(n-1);
}

function calcFactorialWithLoop(n){
  var result = 1;
  for(var i = n; i >= 2; i--){
    result *= i;
  }
  return result;
}

var n = parseInt($('#t0').val());
var result = 
  "再帰関数バージョン: " + n + "! = " + calcFactorialRecursively(n) + "\n" +
  "forループバージョン: " + n + "! = " + calcFactorialWithLoop(n) + "\n";

// メモ化
var fac = {};
function calcFactorialRecursively1(n){
  if(fac) return fac[n];
  if(n <= 1){
    fac[1] = 1;
    return 1;
  }
  fac[n] = n * calcFactorialRecursively1(n-1);
  return fac[n];
}
// メモ化ありと無しの時間を計測してみる
// メモ化無し
var c = parseInt($('#t1').val());
var now = new Date();
for(var i = 1; i <= c; i++){
  calcFactorialRecursively(i);
}
var duration = (new Date() - now) / 1000;
result += "メモ化無し: " + duration + "秒\n";
// メモ化有り
now = new Date();
for(var i = 1; i <= c; i++){
  calcFactorialRecursively1(i);
}
duration = (new Date() - now) / 1000;
result += "メモ化有り: " + duration + "秒\n";
$('#pre0').text(result);

(注意: あまり大きい値を入力するとブラウザが固まる。)

n =
c =

再帰関数でメモ化っていうのに挑戦してみた。実際に速度も速くなったし、これであってるのかな。。

ちなみにPython3kの場合。

コード(TextWrangler)

sample.py

#!/usr/bin/env python3.3
#-*- coding: utf-8 -*-

def calc_factorial_recursively(n):
    if n <= 1: return 1
    return n * calc_factorial_recursively(n-1)

def calc_factorial_with_loop(n):
    result = 1
    for i in range(1, n+1):
        result *= i
    return result

import re
pattern = re.compile(r"^\s*$")
while True:
    print("数値を入力: ", end="")
    str = input()
    if re.match(pattern, str): break
    n = int(str)
    print("再帰版: {0}! = {1}".format(n, calc_factorial_recursively(n)))
    print("forステートメント版: {0}! = {1}".format(n, calc_factorial_with_loop(n)))

fac = {}
def calc_factorial_recursively1(n):
    if n in fac: return fac[n]
    if n <= 1:
      fac[1] = 1
      return fac[1]
    fac[n] = n * calc_factorial_recursively1(n-1)
    return fac[n]

import time
now = time.time()
n = 500
for n in range(1, n): calc_factorial_recursively(n)
print("メモ化無し: {0}秒".format(time.time() - now))

now = time.time()
for n in range(1,n): calc_factorial_recursively1(n)
print("メモ化: {0}秒".format(time.time() - now))

入出力結果(Terminal)

$ ./sample.py
数値を入力: 10
再帰版: 10! = 3628800
forステートメント版: 10! = 3628800
数値を入力: 1
再帰版: 1! = 1
forステートメント版: 1! = 1
数値を入力: 0
再帰版: 0! = 1
forステートメント版: 0! = 1
数値を入力: 11
再帰版: 11! = 39916800
forステートメント版: 11! = 39916800
数値を入力: 
メモ化無し: 0.06978893280029297秒
メモ化: 0.0007331371307373047秒
$