python - 高尔顿代码 - 从递归到迭代

Question

def galton(m, n):
    if m == 0:
        if n == 0:
            return 1
        else:
            return 0
    else:
        if n == 0:
            return 1
        else:
            return (galton(m-1, n-1) + galton(m-1, n))

您好，有人知道我如何将这段代码从递归更改为迭代吗？我用高尔顿公式试过了，但我只得到了概率。

代码：

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer / denom *(0.5**n)

标签： pythonrecursioniteration

Answer 1

您的galton函数似乎只是'nCr' 的递归实现，因此任何 nCr 函数只需稍作改动即可在以下情况下返回零r > n：

def ncr(n, r):
    if r > n:
         return 0
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom