はじめに

「こう実装するともっときれいだよ！」
「こっちの方がいいんじゃない？」
等あれば、コメントお願い致します。

フィボナッチ数とは

n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に
F0 = 0,
F1 = 1,
Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される

最初の2項(0,1)を除き、1つ前と2つ前の和となる

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

いろいろな言語で実装してみた

以下の言語で実装

JavaScript
Java
Ruby
Python
Go
Kotlin

気をつけたこと

普通に再帰するだけにしない(パフォーマンス的に)
- メモ化等する
- ひとまずn = 50までを求められるくらい
なるべく短く記述する

JavaScript

fibonacci.js

// memoize
var fibs = {}

// fibonacci function
function fib(n) {
  if (n <= 1) return n
  if (fibs[n]) return fibs[n]
  return fibs[n] = fib(n-1) + fib(n-2)
}

for (let i = 0; i < 50; i++) {
  console.log(fib(i))
}

Java

Fibonacci.java

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;

public class Fibonacci {

  // memoize
  private static Map<Integer, BigInteger> values = new HashMap<>();

  public static void main(String[] args) {
    for (int i = 0; i < 50; i++) {
      System.out.println(fibonacci(i));
    }
  }

  public static BigInteger fibonacci(Integer n) {
    if (values.containsKey(n)) return values.get(n);
    else if (n == 0) return BigInteger.ZERO;
    else if (n == 1) return BigInteger.ONE;
    else {
      BigInteger fib = fibonacci(n - 1).add(fibonacci(n - 2));
      values.put(n, fib);
      return fib;
    }
  }
}

Ruby

メモ化を使ったパターン

fibonacci.rb

@values = Hash.new

def fib(n)
  return @values[n] if @values[n]
  return n if n <= 1
  return @values[n] = fib(n - 1) + fib(n - 2)
end

50.times do |i|
  puts fib(i)
end

よりシンプルに書くパターン

fibonacci.rb

a, b = 0, 1
50.times do
  puts a
  a, b = b, a + b
end

Python

fibonacci.py

# fibonacci function
def fib(n):
  a, b = 0, 1
  for _ in range(n):
    yield a
    a, b = b, a + b

# print
[ print(i) for i in fib(50) ]

Go

割と公式そのままになってしまった...

fibonacci.go

package main

import (
    "fmt"
)

func main() {
    f := fib()
    for i := 0; i < 50; i++ {
        fmt.Println(f())
    }
}

// fibonacci func
func fib() func() int64 {
    var a, b int64 = 0, 1
    return func() int64 {
        a, b = b, a+b
        return a
    }
}

Kotlin

fibonacci.kt

val fibs = mutableMapOf(0 to 0L, 1 to 1L)

fun main(args: Array<String>) {
  for (i in 0..50) {
    println(fib(i))
  }
}

// fibonacci function
fun fib(n: Int): Long? {
  return if (fibs.containsKey(n)) fibs[n]
        else {
          fibs.put(n, fib(n-1)!!+fib(n-2)!!)
          fibs[n]
        }
}

まとめ

色々な言語で同じアルゴリズムを実装してみると、違いが分かって面白い
基本的なアルゴリズムでも、言語仕様の理解が深まるし勉強になる
GoとかKotlin使いこなしたい

色々な言語でフィボナッチ数を求めるプログラム