Help us understand the problem. What is going on with this article?

フィボナッチ数を求めるコード python版 2例

More than 1 year has passed since last update.

フィボナッチ数とは

n 番目のフィボナッチ数を Fn で表すと、Fn は再帰的に
F0 = 0,
F1 = 1,
Fn + 2 = Fn + Fn + 1 (n ≧ 0)
で定義される。これは、2つの初期条件を持つ漸化式である。
wikipediaより

アルゴリズムの勉強に使われることがあるらしいです。

n番目のフィボナッチ数(上記のFn)を求める関数を考えます

求め方その1 forループ

1つ前、2つ前の値を保持、更新しながら定義どおりに足して求める

def fibonacci(n):
    if n==0:
        return 0 #F0
    elif n==1:
        return 1 #F1
    else:
        fibo_minus1 = 1 #Fn-1
        fibo_minus2 = 0 #Fn-2
        for i in range(2,n):
            fibo = fibo_minus1 + fibo_minus2 #Fn = Fn-1 + Fn-2
            fibo_minus2 = fibo_minus1 # Fn-2の値を更新
            fibo_minus1 = fibo # Fn-1の値を更新
        return fibo

求め方その2 再帰的に求める

解説は省略。
nの値によっては、動作しないです。
(再帰の深さの設定が必要になってきます)

def fibonacci(n):
    if n == 0:
        return 0 # F0
    elif n == 1:
        return 1 # F1
    return fibonacci_sub(n-2, 1, 0) #F2以降

def fibonacci_sub(n, last1, last2):
    if n == 0: # 必要回数足したら最終的な和を返す
        return last1
    else: # 必要回数足すまでは、この部分で再帰的に自分を呼び出しながら、値の保持と更新をする
        return fibonacci_sub(n-1, last1+last2, last1) 

fibonacci_sub()のreturn部分を以下のように後置ifの形にすれば、更に行数圧縮できます。
可読性は・・どうなんだろう。後置if見慣れていれば、スッキリ読めるのかも。

def fibonacci(n):
    if n == 0:
        return 0 # F0
    elif n == 1:
        return 1 # F1
    return fibonacci_sub2(n-2, 1, 0) #F2以降

def fibonacci_sub2(n, fibo_minus1, fibo_minus2):
    return fibo_minus1 if n==0 else fibonacci_sub2(n-1, fibo_minus1+fibo_minus2, fibo_minus1)
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away