フィボナッチ数の漸化式

F0 = 0
F1 = 1
Fn+2 = Fn+1 + Fn

再帰で求めるアルゴリズムは以下です。(C#のサンプル)

using System;

class Fib {
  public static int fib(int n) {
  if (n < 2) return n;
  return fib(n - 2) + fib(n - 1);
  }

  static void Main() {
  Console.WriteLine(fib(38));
  }
}

PowerShellで再帰

元ソースのやり方をPowerShellで書くと以下になります。

function fib([int]$n) {
  if ($n -lt 2) { return $n }
  return (fib($n -2)) + (fib($n -1))
}

fib 38

さて、肝心の実行速度は……… はい、測定不可です。現実的に待てる程度の実行対象は30程度までです。 n=19 - 20程度まではそれなりなんですけどねー。

蛇足

function名をそれっぽくして、whileをいれて0から29まで順次実行させるとこうでしょうか… ※どんどん遅くなるのが一目瞭然ですねorz

function Get-Fib {

  param(
  [int]$n
  )

  if ($n -lt 2) { return $n }
  return (fib($n -2)) + (fib($n -1))

}

$x = 0
while ($x -lt 39)
{
  Get-Fib $x
  $x++
}

whileなんて使うな? はい、そうですね。連番生成して、パイプで渡し、Foreach-Objectにてぐるぐる回しましょう。

function Get-Fib {
  param([int]$n)

  if ($n -lt 2) { return $n }
  return (fib($n -2)) + (fib($n -1))
}

0..38 | ForEach-Object{ Get-Fib $_ }

再帰で時間がかかる原因

これは、以下のサイトで解説している通り、再帰実行での繰り返し呼び出しに依る問題です。

ActionScript入門Wiki　-　再帰処理(フィボナッチ数編)

値	関数の呼び出し回数
fibonacci(3)	5
fibonacci(5)	15
fibonacci(8)	67
fibonacci(10)	177
fibonacci(20)	21891
fibonacci(30)	2692537

最適化できないの?

それなら、n-1の実行値を保存させればいいということで、最適化を書こうかと思ったのですが……

function fib([int]$n,[int]$cur=1,[int]$prev=0) {
  if ($n -eq 0) { return 0 }
  if ($n -eq 1) { return $cur }
  return (fib($n -1),($cur + $prev),$cur)
}

fib 10

以下のコード部分がCASTエラーではじかれ…ぐぬぬ

return (fib($n -1),($cur + $prev),$cur)

fib : パラメーター 'n' の引数変換を処理できません。"System.Object[]" の値を "System.Object[]" 型から "System.Int32" 型に変換できません。
発生場所 行:5 文字:20
+   return (fib($n -1),($cur + $prev),$cur)
+      ~~~~~~~~~~~~~~~~~~~~~~~~~~~
  + CategoryInfo    : InvalidData: (:) [fib]、ParameterBindingArgumentTransformationException
  + FullyQualifiedErrorId : ParameterArgumentTransformationError,fib

そもそも、PowerShellの再帰にはこんな制限が……

呼び出しの深さのオーバーフローのため、スクリプトが失敗しました。呼び出しの深さが 101 に達しましたが、最大値は 100 です。

PowerShellならパイプラインでしょ

さて、冷静に考えましょう。PowerShellの武器は。そう、パイプラインですね。で、さくさく書いたら出来ました. ※n=3から出力されています。

1..36 | ForEach-Object{ $i = $prev = 1 }{ $curr = $i+$prev; $i=$prev; $prev=$curr; $curr }

n=0,1,2の場合もいれろ? あ、はい。

begin{$x=0;while($x -lt 2){$x;$x++}if($x -eq 2){$x - ($x-1)}} process{1..36 | ForEach-Object{ $x = $prev = 1; }{[decimal]$curr = $x+$prev; $x = $prev; $prev = $curr; $curr}}

改行です。

begin{

  $x=0

  while( $x -lt 2 )
  {
  $x
  $x++
  }

  if ($x -eq 2)
  {
  $x - ($x-1)
  }
}

process{

  1..137 | ForEach-Object { $x = $prev = 1 } {
    [decimal]$curr = $x+$prev
    $x = $prev
    $prev = $curr
    $curr
  }
}

[decimal]型の最大として0..137までは出力されます。

begin{$x=0;while($x -lt 2){$x;$x++}if($x -eq 2){$x - ($x-1)}} process{1..137 | ForEach-Object{ $x = $prev = 1; }{[decimal]$curr = $x+$prev; $x=$prev; $prev=$curr; $curr}};

再帰の問題を回避しているので、0..137も一瞬で出力されます。 Measure-Commandで測定すると0.11秒でした。

#Measure-Commandで実行時間測定
begin{$x=0;while($x -lt 2){$x;$x++}if($x -eq 2){$x - ($x-1)}} process{Measure-Command{1..137 | ForEach-Object{ $x = $prev = 1; }{[decimal]$curr = $x+$prev; $x=$prev; $prev=$curr; $curr}}};

Days    : 0
Hours     : 0
Minutes     : 0
Seconds     : 0
Milliseconds  : 11
Ticks     : 119224
TotalDays   : 1.37990740740741E-07
TotalHours  : 3.31177777777778E-06
TotalMinutes  : 0.000198706666666667
TotalSeconds  : 0.0119224
TotalMilliseconds : 11.9224