algorithm - T(0) = 1, T(1) = 0, T(n ) = 2* T(n-2) 的递归关系

我试图找到上述表达式的递归关系。

我推断:

T(n) = C*T(n-2)

T(n-2) = 2C*T(n-4)

T(n-4) = 3C * T(n-6)

...

T(n) = k/2C * T(n-k)

我被困在这里了。这是正确的方法吗？什么是简化方程中没有T的简化递归关系？

最佳答案

我写了一个python程序，找到了关系:

def rec(num):
    if num == 0:
        return 1
    elif num == 1:
        return 0
    else:
        return 2 * rec(num - 2)

经过多次测试，我发现了这个规律:

index 2, 3, 4, 5, 6, 7, 8....

result 2, 0, 4, 0, 8, 0, 16....

所以结果可能是 2^(n/2) when n = 2k && 0 when n = 2k + 1 (k belongs to Z)

关于algorithm - T(0) = 1, T(1) = 0, T(n ) = 2* T(n-2) 的递归关系，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46750223/