我知道这种类型的方程可以用许多方法来解决,但我想使用递归树方法来解决这个方程。有人能向我展示如何使用递归树方法吗?
我知道这种类型的方程可以用许多方法来解决,但我想使用递归树方法来解决这个方程。有人能向我展示如何使用递归树方法吗?
F(n) = F(n-1) + F(n-2)
int fib(int x) {
if (x == 0)
return 0;
if (x == 1)
return 1;
return fib(x-1)+fib(x-2); //Does this recurrence look familiar?
}
对于输入5,它会产生以下树形结构:
5
/ \
/ \
/ \
/ \
/ \
/ \
/ \
4 3
/ \ / \
/ \ / 1
/ \ 2
3 2 / \
/ \ / \ 1 0
/ \ / \
2 1 1 0
/ \
/ \
1 0
上面,我画了一个非常简单的斐波那契数列递归树。我只是插入了第一个数字(5),并继续从其后续的递归调用中产生一个简单的树形结构。你可以看到树的高度是N,分支因子是2,因此我们的上限必须是O(2^n)。你可以通过推广这个方法来得到你想要找到的特定问题的答案以及任何其他递归关系式。
T(0)=0
和T(1)=0
? - fafl