我的 Pascal 三角程序中这个神秘数字来自哪里？

Question

我写了一个数字输出帕斯卡三角的第n行：

import sys
def nth_row_pascal(n):

    def nth_num(i, j):

        if i==0:
            print("({},{}) determined to be 1".format(i,j))
            return 1
        if (j == 0) or (j==i):
            print("({},{}) determined to be 1".format(i,j))            
            return 1
        print("calculating pascal number: ({},{})".format(i,j))                
        result=nth_num(i-1, j-1) + nth_num(i-1, j)
        print("answer: " + str(result))
        return result

    result = [nth_num(i, int(n)-1) for i in range(int(n))]
    return result

print(nth_row_pascal(sys.argv[1]))

当我运行

python pascal.py 4

我得到：

python3 pascal.py 4
(0,3) determined to be 1
calculating pascal number: (1,3)
(0,2) determined to be 1
(0,3) determined to be 1
answer: 2
calculating pascal number: (2,3)
calculating pascal number: (1,2)
(0,1) determined to be 1
(0,2) determined to be 1
answer: 2
calculating pascal number: (1,3)
(0,2) determined to be 1
(0,3) determined to be 1
answer: 2
answer: 4
(3,3) determined to be 1
[1, 2, 4, 1]

为什么是

answer: 4 弹出？

函数 nth_num 似乎会打印出一条语句 --

i,j determined to be 1 或
calculating pascal number ...

但在这种情况下 answer: 2（可以理解） answer: 4（什么？？）

每次执行。

Answer 1

在 "calculating" 和 "answer" 行之间发生了很多事情，包括其他递归调用！这里有一些 ASCII 艺术和一些额外的空格，以帮助清除 answer: 4 的确切来源：

(0,3) determined to be 1

calculating pascal number: (1,3)  >-----\
(0,2) determined to be 1                |
(0,3) determined to be 1                |
answer: 2   <---------------------------/

calculating pascal number: (2,3)  >-----\
                                        |
calculating pascal number: (1,2)  >-\   |
(0,1) determined to be 1            |   |
(0,2) determined to be 1            |   |
answer: 2   <-----------------------/   |
                                        |
calculating pascal number: (1,3)  >-\   |
(0,2) determined to be 1            |   |
(0,3) determined to be 1            |   |
answer: 2   <-----------------------/   |
                                        |
answer: 4   <---------------------------/

(3,3) determined to be 1

在跟踪递归函数以了解它们的工作原理时，它可以帮助打印出递归调用的深度，如下所示：

from typing import List


def nth_row_pascal(arg: str) -> List[int]:
    n = int(arg)

    def nth_num(i: int, j: int, depth: int) -> int:
        indent = "  " * depth  # for pretty-printing
        if i == 0:
            print(f"{indent}{(i, j)} determined to be 1")
            return 1
        if j in {0, i}:
            print(f"{indent}{(i, j)} determined to be 1")
            return 1
        print(f"{indent}calculating pascal number: {(i, j)}")
        result = nth_num(i-1, j-1, depth+1) + nth_num(i-1, j, depth+1)
        print(f"{indent}answer: {result}")
        return result

    result = [nth_num(i, n-1, 0) for i in range(n)]
    return result

(0, 3) determined to be 1
calculating pascal number: (1, 3)
  (0, 2) determined to be 1
  (0, 3) determined to be 1
answer: 2
calculating pascal number: (2, 3)
  calculating pascal number: (1, 2)
    (0, 1) determined to be 1
    (0, 2) determined to be 1
  answer: 2
  calculating pascal number: (1, 3)
    (0, 2) determined to be 1
    (0, 3) determined to be 1
  answer: 2
answer: 4
(3, 3) determined to be 1
[1, 2, 4, 1]

我的 Pascal 三角程序中这个神秘数字来自哪里？

where is this mystery number coming from in my pascal's triangle program?

python

recursion

pascals-triangle