python3で再帰関数

5085 ワード
再帰関数 Python3 Python3 テキストリンク

はじめに

私が再帰関数についてわかったことを共有します。

　Code

python3.6
i = 0

def sum(n):
    global i
    i = i + 1
    print(i)

    if n <= 0:
        return n

    result = n + sum(n - 1)

    # print
    print("n         : {}".format(n))
    print("n-1       : {}".format(n-1))
    print("n + (n-1) : {}".format(result))
    print("--------------")
    return result

sum(3)

　解説

を実行すると

sum(3)の場合

couunt    : 1回
couunt    : 2回
couunt    : 3回
couunt    : 4回
n         : 1
n-1       : 0
n + (n-1) : 1
--------------
n         : 2
n-1       : 1
n + (n-1) : 3
--------------
n         : 3
n-1       : 2
n + (n-1) : 6
--------------

では10回なら

couunt    : 1回
couunt    : 2回
couunt    : 3回
couunt    : 4回
couunt    : 5回
couunt    : 6回
couunt    : 7回
couunt    : 8回
couunt    : 9回
couunt    : 10回
couunt    : 11回
n         : 1
n-1       : 0
n + (n-1) : 1
--------------
n         : 2
n-1       : 1
n + (n-1) : 3
--------------
n         : 3
n-1       : 2
n + (n-1) : 6
--------------
n         : 4
n-1       : 3
n + (n-1) : 10
--------------
n         : 5
n-1       : 4
n + (n-1) : 15
--------------
n         : 6
n-1       : 5
n + (n-1) : 21
--------------
n         : 7
n-1       : 6
n + (n-1) : 28
--------------
n         : 8
n-1       : 7
n + (n-1) : 36
--------------
n         : 9
n-1       : 8
n + (n-1) : 45
--------------
n         : 10
n-1       : 9
n + (n-1) : 55
--------------

になります。

3　+　sum(3 - 1)
　　　　　|　2
　　　　sum(2 - 1)　+　sum(1 - 1)
　　　　　　　　　　　　　　|　１
　　　　　　　　　　　　sum(1-1)　+　sum(0-1)
　　　　　　　　　　　　　　　　　　　　|　０
　　　　　　　　　　　　　　　　　　　sum(0-1)
　　　　　　　　　　　　　　　　　　　ifの判定がTrueになるのでnがreturnされて
　　　　　　　　　　　　　　　　　　　下のreturn resultまでは行かずに終了する。

3 + 
    (3-1 + 
          (2-1 + 
                (1-1 + 
                      (0-1))))

このようなイメージ

　参考

多大に参考にさせて頂きました。

再帰関数を理解するための最もシンプルな例

終わりに

自分のイメージなので他の人が分かりやすいかは分かりませんが参考になれば幸いです。