斐波那契调用堆栈中叶子与总节点的比率
如果您要查看计算第 n 个斐波那契数（根 100，子数 99 和 98，孙子 98、97、97 和 96 等）的递归实现，则大致的数量比率是多少叶子数除以递归树的节点总数？
100
/ \
98 97
/ \ .
96 97 .
. . .
. .
不是作业，只是对此感到学术上的好奇。 （是的，我意识到递归实现是计算斐波那契数的一种糟糕的方法）
If you were to look at a recursive implementation of calculating the nth Fibonacci number (root 100, children 99 and 98, grandchildren 98, 97, 97, and 96, etc. etc.), roughly what would be the ratio of the number of leaves to the total number of nodes in the recursive tree?
100
/ \
98 97
/ \ .
96 97 .
. . .
. .
Not homework, just academically curious about this. (And yes, I realize that a recursive implementation is a god-awful way to calculate Fibonacci numbers)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
叶子的数量就是
F(n)，因为F(i)只是该节点下叶子的数量。你明白为什么吗？ （提示：使用归纳法）非叶子节点的数量是叶子节点的数量-1。这是二叉树的一个性质。因此节点总数为
F(n) + F(n)-1 = 2F(n)-1。因此，随着 n 变大，该比率接近1/2。
The number of leaves is simply
F(n)since theF(i)is simply the number of leaves beneath that node. Do you see why? (hint: use induction)The number of non-leaf nodes is the number of leaf nodes-1. This is a property of binary trees. So the total number of nodes is
F(n) + F(n)-1 = 2F(n)-1.The ratio thus approaches 1/2 as n grows large.
fib(x) 由叶子 fib(x-1) 和叶子 fib(x-2) 组成。因此，您将得到与斐波那契数相同的递归方程。
如果终止点（叶子）是 Fib1 和 Fib0，则
numofleaves(x) = fib(x+1)。
对于节点数，您可以得到方程 numnodes(x) = 1 + numnodes(x-1) + numnodes(x-2)。
fib(x) consist of leaves fib(x-1) and leaves of fib(x-2). So you get the same recursive equation as you have for fibonacci numbers.
If the termination point (leaves) are Fib1 and Fib0, then
and numofleaves(x) = fib(x+1).
For the number of nodes you get the equation numnodes(x) = 1 + numnodes(x-1) + numnodes(x-2).
我实际上通过归纳法得出了一个证明，表明斐波那契树中叶子的数量总是超过内部节点的数量。
证明：设 E(n) 为输入 n 的斐波那契树的叶子数，
M(n) 是输入 n 的斐波那契树的内部节点数
基本情况：
f(0): E(0) = 1, M(0) = 0
f(1): E(1) = 1, M(1) = 1
f(2): E(2) = 2, M(2) = 1
f(3): E(3) = 3, M(3) = 2
大小为 n 的树的叶子等于叶子
每个子树的内部节点：
E(n) = E(n - 1) + E(n - 2)
大小为 n 的树的内部节点等于每个子树的内部节点
子树，加上根
M(n) = M(n - 1) + M(n - 2) + 1
E(n) >= [M(n - 1) + 1] + [M(n - 1) 2) + 1], （通过归纳假设）
所以，E(n) = M(n - 1) + M(n - 2) + 2
所以，E(n) >= M(n) + 1，
量子电动力学
I actually worked out a proof by induction that shows that the number of leaves in a Fibonacci tree always exceeds the number of internal nodes.
Proof: Let E(n) be the # of leaves of fibonacci tree for input n,
and M(n) be the # of internal nodes of fibonacci tree for input n
Base cases:
f(0): E(0) = 1, M(0) = 0
f(1): E(1) = 1, M(1) = 1
f(2): E(2) = 2, M(2) = 1
f(3): E(3) = 3, M(3) = 2
The leaves of a tree of size n is equal to the leaves
of each sub-tree:
E(n) = E(n - 1) + E(n - 2)
The internal nodes of a tree of size n is equal to the internal nodes of each
sub-tree, plus the root
M(n) = M(n - 1) + M(n - 2) + 1
E(n) >= [M(n - 1) + 1] + [M(n - 2) + 1], (by the Inductive Hypothesis)
So, E(n) = M(n - 1) + M(n - 2) + 2
So, E(n) >= M(n) + 1,
QED