バグあり！ 独学コンピューターサイエンティスト 第１部 第２章 再帰 について

独学コンピューターサイエンティスト 第１部 第２章 再帰 を読んで、まず再帰版の factorial 関数が不必要に一度多く自分自身を呼んでいる気がしました。

実際に、それを確かめたサンプルプログラムとその実行結果を示します。

# 独学コンピューターサイエンティスト 第１部 第１章 のオリジナル再帰関数 factorial()

def factorial(n):
    if n == 0:
        return 1
        
    return n * factorial(n - 1)

print("factorial(3) =", factorial(3), "\n")


# factorial(3) の時、正しい階乗 3 × 2 × １ 計算になっているか確かめる為に factorial() を改変！

def factorial_2(n):
    if n == 0:
        print(f"    n = {n}  return 1")
        return 1
        
    ret = n * factorial_2(n - 1)
    print(f"    n = {n}  return {ret}")
    
    return ret

print("factorial_2(3) =",factorial_2(3), "\n")


# 実行結果を見ると 3 × 2 × １ × １ になっているので修正してみる！

def factorial_de(n):
    if n == 1:  ##### n == 0 を n == 1 に修正 #####
        print(f"    n = {n}  return 1")
        return 1
        
    ret = n * factorial_de(n - 1)
    print(f"    n = {n}  return {ret}")
    
    return ret

print("factorial_de(3) =",factorial_de(3), "\n")


# 実行結果を見ると、これで 3 × 2 × １ になったので最終的な factorial() を最後に示して終わり！

def factorial_new(n):
    if n == 1:  ##### n == 0 を n == 1 に修正 #####  まあ、本当は n <= 1 の方が安全なんだけどね・・・
        return 1
        
    return n * factorial_new(n - 1)

print("factorial_new(3) =", factorial_new(3), "\n")

実行結果

factorial(3) = 6 

    n = 0  return 1
    n = 1  return 1
    n = 2  return 2
    n = 3  return 6
factorial_2(3) = 6 

    n = 1  return 1
    n = 2  return 2
    n = 3  return 6
factorial_de(3) = 6 

factorial_new(3) = 6 

後、内部スタックと言う言葉に違和感を感じました。評価が確定していない戻り値がスタックに積み上げられているように見えるという概念的な意味で使われているなら分かります。それなら例えば、Python の、コールされた関数のローカルなシンボル表なども内部スタックに含まれるかもしれません。ただし、実際の実装の話となると？？

それに、そもそも、計算出来ない中間結果を記憶する必要が無い、全ての中間結果が計算可能な再帰処理も書けます。全ての再帰処理が、計算出来ない中間結果を記憶しなければならない分けではありません。これはアルゴリズムしだいです。

最後に、計算出来ない中間結果を記憶する必要が無い、全てが計算出来る階乗再帰処理関数を示しておきます。オリジナルの factorial 関数と機能は同じです。

def factorial_x(n, ret=1):  # 1 は必ず掛けるので、最初に掛けるデフォルト値は １
    if n == 1:
        return ret  # 1 は最初に掛けてあるのでそのままリターン
        
    return factorial_x(n - 1, ret * n)  # 中間計算結果を保持する必要が無い！！

print("factorial_x(3) =", factorial_x(3), "\n")

実行結果

factorial_x(3) = 6 

#独学コンピューターサイエンティスト #独CS #selftaughtcoder
#Python #Python3
#再帰処理 #再帰