如何在Python中解决递归关系

我正在尝试编写代码来给出递归关系的数值答案。该关系本身很简单，定义如下。变量 x 是一个整数

• p(i) = p(i+2)/2 + p(i-1)/2 如果 i > 0 且 i
• p(0) = p(2)/2
• 如果 i >= x，则 p(i) = 1

这也在这段代码中。

from __future__ import division
def p(i):
    if (i == 0):
        return p(2)/2
    if (i >= x):
        return 1
    return p(i-1)/2+p(i+2)/2


x = 4
#We would like to print p(0)  for example.

当然，这实际上并不能让您计算 p(0)。你怎么能在Python中做到这一点？

是否可以建立一个联立方程组numpy.linalg.solve那么可以解决吗？

你是对的，这可以使用线性代数来解决。我下面所做的是一个简单的硬编码翻译。你的方程p(0) to p(3)通过重新排列它们来编码，以便右侧是=0. For p(4) and p(5)作为基本情况出现在递归关系中，有一个=1在右手侧。

• -p(0) + p(2)/2 = 0

• p(i-1)/2 - p(i) + p(i+2)/2 = 0对于 i > 0 且 i

• p(i) = 1如果我 >= x

这是硬编码的程序n=4

import numpy
a=numpy.array([[-1,   0, 0.5,  0,   0,   0], # 0
               [0.5, -1,   0,0.5,   0,   0], # 1
               [0,  0.5,  -1,  0, 0.5,   0], # 2
               [0,    0, 0.5, -1,   0, 0.5], # 3
               [0,    0,   0,  0,   1,   0], # 4
               [0,    0,   0,  0,   0,   1], # 5
              ])
b=numpy.array([0,0,0,0,1,1])
# solve ax=b
x = numpy.linalg.solve(a, b)
print x

Edit，这里是以编程方式构造矩阵的代码，仅经过测试n=4!

n = 4

# construct a
diag = [-1]*n + [1]*2
lowdiag = [0.5]*(n-1) + [0]*2
updiag = [0.5]*n
a=numpy.diag(diag) + numpy.diag(lowdiag, -1) + numpy.diag(updiag, 2)

# solve ax=b
b=numpy.array([0]*n + [1]*2)
x = numpy.linalg.solve(a, b)

print a
print x[:n]

这输出

[[-1.   0.   0.5  0.   0.   0. ]
 [ 0.5 -1.   0.   0.5  0.   0. ]
 [ 0.   0.5 -1.   0.   0.5  0. ]
 [ 0.   0.   0.5 -1.   0.   0.5]
 [ 0.   0.   0.   0.   1.   0. ]
 [ 0.   0.   0.   0.   0.   1. ]]
[ 0.41666667  0.66666667  0.83333333  0.91666667]

这与您问题下评论中的解决方案相匹配。