7
$\begingroup$

I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts fibtree(2) as

enter image description here

and fibtree(3) as

enter image description here

I thought fibtree(3) looks like the following

enter image description here

(the figure is adapted from another StackOverflow post).

Do I misunderstand something? Or is the Berkeley tutorial misusing the figures?

$\endgroup$
1
  • 8
    $\begingroup$ The trees are the same; only the labels are different, so you have to know what the labels mean in both cases before you decide whether either one is right or wrong. $\endgroup$
    – chepner
    Jan 10, 2022 at 16:33

2 Answers 2

Reset to default
21
$\begingroup$

I would like to say both you and that Berkeley tutorial are correct.

As commented by chepner, the trees in Berkeley tutorial and the trees you thought are the same semantically; only the labels of the nodes are different.

Every node in all figures represents a call to compute the corresponding Fibonacci number.

The difference is that you prefer to use strings "F(0)", "F(1)", "F(2)", etc. to represent the calls that compute the 0-th Fibonacci number, the 1-st Fibonacci number, the 2-nd Fibonacci number, etc. respectively while the Berkeley tutorial uses those Fibonacci numbers themselves, $0, 1, 1$, i.e., the results of those calls to represent the same calls respectively.

Your preference is more illustrative since the string "F(0)", "F(1)", "F(2)", "F(3)", etc. are obviously descriptive while the Fibonacci numbers $0, 1, 1, 2$, etc. do not indicate the calls immediately without additional explanation. Furthermore, both the node representing the call "F(1)" and the node representing a different call "F(2)" are labelled $1$ in Berkeley tutorial, which may lead to confusion.

$\endgroup$
5
  • $\begingroup$ It sounds like you're saying the Berkeley tutorial is using $1$ as a shorthand for "F(1)", but that is not true. The Berkeley tutorial is simply showing the result of the call in each node, rather than the calls themselves. $\endgroup$
    – JounceCracklePop
    Jan 11, 2022 at 8:00
  • 1
    $\begingroup$ @JounceCracklePop, "simply showing the result of the call in each node" is a valid interpretation of the figures in the Berkeley tutorial. However, the Berkeley tutorial introduces "Fibonacci trees" as "trees that represents the recursive call structure of the Fibonacci computation" instead of "trees that represents the all intermediate results of the Fibonacci computation". $\endgroup$
    – John L.
    Jan 11, 2022 at 8:23
  • 2
    $\begingroup$ The tree indeed represents the recursive call structure, regardless of how it's labeled. It might be a confusing tree if unlabeled, but it would still provide insight on the recursion (e.g. count the nodes for total # of calls, count max depth to detect stack overflow, etc.) You might disagree with how Berkeley is labeling their tree, but your answer seems to misunderstand their labeling, rather than simply disagree with it. $\endgroup$
    – JounceCracklePop
    Jan 11, 2022 at 8:27
  • 1
    $\begingroup$ "It sounds like you're saying the Berkeley tutorial is using 1 as a shorthand for "F(1)" This is a slight misunderstanding of my answer. My answer interprets the Berkeley tutorial as using $1$ to represent the call $F(1)$ (and the call $F(2)$). $\endgroup$
    – John L.
    Jan 11, 2022 at 9:03
  • $\begingroup$ All comments above can be ignored now. $\endgroup$
    – John L.
    Jan 11, 2022 at 19:07
7
$\begingroup$

Your trees are showing the same thing; you are just labeling each node by the call, and the Berkeley tutorial is labeling each node by the result of that call. Compare the two pictures of fibtree(3), noting that:

$F(0) = 0$

$F(1) = 1$

$F(2) = 1$

$F(3) = 2$

You'll see there's no disagreement at all.

Perhaps it would be informative to see the tree "grow" over time as the calls are made and resolved. If we define $F(0) = 0$, $F(1) = 1$, and $F(x) = F(x-1) + F(x-2)$ for $x>1$, we can visualize how we compute $F(3)$ with a tree, where each node is a function call. I will label nodes as $F(x)$ when we don't know the answer yet, and label them with a purple number when we do.

We want to know $F(3)$:

F(3)

Since $3>1$, we call $F(3-1)$ and $F(3-2)$ and wait for the result.

F(3) expands into F(2) and F(1)

Since $2>1$, we call $F(2-1)$ and $F(2-2)$ from that node, and wait for the result. This is your picture.

Fully expanded call, no base case yet.

We can immediately replace $F(0)$ with $0$ based on our function definition, and then return, making no further calls.

F(0) replaced with 0

We can also replace all $F(1)$ calls with $1$ by our definition.

F(1) replaced with 1

We can now evaluate $F(2)$ by adding the results of its child calls, $1+0$

F(2) found by adding its children

And finally we can find $F(3)$ by adding the results of its child calls, $1+1$. This is Berkeley's picture.

F(3) found by adding children

Hopefully that clarifies the relationship between the two pictures.

$\endgroup$
6
  • $\begingroup$ What is the meaning of each node itself? I would say each node represents the call to compute that number in either figure. What is your explanation? $\endgroup$
    – John L.
    Jan 11, 2022 at 8:33
  • $\begingroup$ @JohnL. see my edits. Does that clarify things? $\endgroup$
    – JounceCracklePop
    Jan 11, 2022 at 8:53
  • $\begingroup$ Yes, you wrote "each node is a function call". That is exactly my preferred interpretation of both figures in my answer. $\endgroup$
    – John L.
    Jan 11, 2022 at 8:58
  • 1
    $\begingroup$ Now I see your misunderstanding. If you checked the clause "while the numbers 0,1,1,2 do not indicate the call" in my answer, you can see that by "those numbers themselves", I meant the Fibonacci numbers, just as in your answer, not the indices of the Fibonacci numbers. That phrase, "those numbers themselves" is indeed ambiguous, especially when I boldfaced the ordinal incidentally, although the numbers we are talking about have been Fibonacci numbers all the time! To clarify, I will change "those numbers themselves" to "those Fibonacci numbers themselves" in my answer. $\endgroup$
    – John L.
    Jan 11, 2022 at 9:26
  • 1
    $\begingroup$ All comments above can be ignored now. $\endgroup$
    – John L.
    Jan 11, 2022 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.