再帰関数と非再帰関数

n 段の階段を，「1段，2段まとめ（1段飛ばし），3段まとめ（2段飛ばし）で昇る」を組み合わせると，昇り方は何通りあるか。

再帰的に考えればよいのだが，まじめにやると，n が大きくなると大変時間がかかる。

kaisuu = function(n) {
  if (n == 0) {
    return(1)
  } else if (n == 1) {
    return(Recall(n-1))
  } else if (n == 2) {
    return(Recall(n-1) + Recall(n-2))
  } else {
    return(Recall(n-1) + Recall(n-2) + Recall(n-3))
  }
}

> system.time(print(kaisuu(20)))
[1] 121415
   ユーザ   システム       経過  
     0.428      0.003      0.444
> system.time(print(kaisuu(30)))
[1] 53798080
   ユーザ   システム       経過  
   167.456      0.850    173.378

余計な再帰呼び出しが少なくなるようにしただけでも，実行時間は短くなる。

kaisuu2 = function(n) {
  if (n == 0) {
    return(1)
  } else if (n == 1) {
    return(1)
  } else if (n == 2) {
    return(2)
  } else {
    return(Recall(n-1) + Recall(n-2) + Recall(n-3))
  }
}

> system.time(print(kaisuu2(20)))
[1] 121415
   ユーザ   システム       経過  
     0.203      0.002      0.212
> system.time(print(kaisuu2(30)))
[1] 53798080
   ユーザ   システム       経過  
    90.573      0.597     95.541

しかし，再帰を用いないプログラムは問題なく速い。

kaisuu3 = function(n) {
  way = 0
  for (s1 in 0:n) {
    for (s2 in 0:(n%/%2)) {
      for (s3 in 0:(n%/%3)) {
        if (s1+2*s2+3*s3 == n) {
          way = way + factorial(s1+s2+s3)/factorial(s1)/factorial(s2)/factorial(s3)
        }
      }
    }
  }
  way
}

> system.time(print(kaisuu3(20)))
[1] 121415
   ユーザ   システム       経過  
     0.002      0.000      0.002
> system.time(print(kaisuu3(30)))
[1] 53798080
   ユーザ   システム       経過  
     0.014      0.000      0.023

しかし，まあ，この問題は「1段と2段で昇る」というのは Web ページにもよく見られるが，フィボナッチ数列の一般化ということで，以下のようにプログラムすれば所要時間は「検出限界以下」である。

kaisuu4 = function(n) {
  x = 1
  y = 2
  z = 4
  for (i in 4:n) {
    a = x+y+z
    x = y
    y = z
    z = a
  }
  z
}