[python]再帰アルゴリズム

def solution(x):
    if x == 1 or x==0:
        return x
    else:
        return solution(x-1)+solution(x-2)

再帰アルゴリズム:与えられた問題において,同類のより容易な問題の答えでその問題を解くことができれば,同じアルゴリズムを繰り返し適用することで解くことができる.

終了条件を明確にしなければならない.

また,文字を利用した文字アルゴリズムと比較することもできる.

def solution(x):
    fn_1 = 1 ##f1
    fn_2 = 0 ##f0
    fn = x
    while x>=2:
        fn = fn_1 + fn_2
        fn_2 = fn_1
        fn_1 = fn
        x -= 1
    return fn

複文と複文の複雑さはいずれもO(n)であるが,複文は効率的であることが多い.(通常、ゲートプールの方が時間効率が高い)
->組み合わせの数
->ハノイタワー
->フィボナッチソート
これらの問題は再帰アルゴリズムで解決することもできる:直観的で、アルゴリズムが簡単で、説明しやすい利点