再帰によるべき乗（累乗）の計算をいくつか

再帰によりxのn乗を求める。すごく初歩的な問題だと思うが、あらためて。

n回再帰

(defun power (x n) "X to the Nth power"
  (if (<= n 0)
      1
    (* x (power x (- n 1)))))
power
(power 2 8)
=> 256

別解その1: 2乗を利用して再帰呼び出し回数を減らす

(defun power (x n)
  (cond
   ((<= n 1) x)
   ; nが偶数の場合にnを半減させる
   ((evenp n) (funcall (lambda (x) (* x x)) (power x (/ n 2))))
   (t (* x (power x (- n 1))) )))

別解その2: さらに再帰呼び出しを減らす（Perlで書いてるけど）

sub pow3{
    my ($x, $n) = @_;
    if($n < 1){
        1;
    }elsif($n % 2 == 0){
        (sub { my $x=shift; return $x*$x; })->( pow3($x, $n / 2) );2
    }else{
        # nが奇数の場合
        $x * (sub { my $x=shift; return $x*$x; })->( pow3($x, ($n - 1) / 2) );
    }
}

たいていの人は最初の解法で満足するだろう。が、"Paradigms of Artificial Intelligence Programming" という本には2番目の解法が載っていた。すごい人は些細な問題に対してもこだわりが違うのだな、と。