フィボナッチ数列を求めるプログラムのサンプル

FizzBuzz問題をあれこれ考えていたら，『フィボナッチ数列を（とりあえず）45個生成して表示するプログラムを作成しなさい』という問題も，プログラミングに関するある種の指標になるのではなかろうかと思い始めていたり．何が言いたいかは，この記事のタグとサンプルコードのコメント文を参照．

なお，下記サンプルプログラム（コメント記載分は除外）の実行はこちらのサイトで確認済．

#Cの場合

fib.c

#include <stdio.h>

// #define NOT_TAILRECUR

#ifdef NOT_TAILRECUR
unsigned long long fib(int x)
{
  if (x == 0)
    return (0);
  else
  if (x == 1)
    return (1);
  else
    return (fib(x-1) + fib(x-2));
}
#else
unsigned long long fib_r(
  int x,
  unsigned long long a,
  unsigned long long b)
{
  if (x == 0)
    return (a);
  else
    return (fib_r(x-1, b, a+b));
}
unsigned long long fib(int x)
{
  return (fib_r(x, 0, 1));
}
#endif

int main(void)
{
  for (int n = 0; n < 45; n++)
    printf("%llu ", fib(n));
  printf("\n");
  return (0);
}

#Pythonの場合

fib.py

#### not tail-recur
#def fib(x):
#    if x == 0:
#      return (0)
#    elif x == 1:
#      return (1)
#    else:
#      return (fib(x-1) + fib(x-2))

def fib(x):
  def fib_r(x,a,b):
      if x == 0:
        return (a)
      else:
        return (fib_r(x-1, b, a+b))
  return (fib_r(x,0,1))

for i in range(45):
  print(fib(i), "", end="")

#Schemeの場合

fib.scm

;;;; not tail-recur
;(define fib
;  (lambda (x)
;    (cond ((equal? x 0) 0)
;          ((equal? x 1) 1)
;          (else
;            (+ (fib (- x 1)) (fib (- x 2)))))))

(define fib
  (lambda (x)
    (let loop ((x x) (a 0) (b 1))
      (if (equal? x 0) a (loop (- x 1) b (+ a b))))))

(print (map fib (iota 45)))