What is the order of traversal in this recursive fibonacci function?

[gfd43tg]

Hello,

There are three different orders of traversal that we learned about
$\bullet$ pre-order traversal
$\bullet$ in-order traversal
$\bullet$ post-order traversal

Anyone know of any easy ways of remembering these 3 and how to order them? I have posted my lecture slides, but I could imagine the tree looking differently and then not knowing how to adapt and analyze how the calls would be made to a different looking tree.

Also, when one writes a recursive program, which order of traversal is taken? Is there some sort of default? Why are there 3 ways of traversing?

 

[.Scott]

If you write a recursive function (R) to print (P) each node on the tree, you have these choices:
R(this) { if(this) {P(this); R(this->left); R(this-right) } }
R(this) { if(this) {R(this->left); P(this); R(this-right) } }
R(this) { if(this) {R(this->left); R(this-right); P(this) } }

Note how each yields a different print order.

 

[jtbell]

Also, when one writes a recursive program, which order of traversal is taken? Is there some sort of default?

There's no default. It's up to you to decide how you want to traverse a binary tree.

Why are there 3 ways of traversing?

There are actually more than three ways. Consider your "ingredients:"

• A. Process the data in the node that you're pointing to.
• B. Process the subtree that the node's left link points to.
• C. Process the subtree that the node's right link points to.

How many different sequences can we perform these three items in?

A, B, C
A, C, B
B, A, C
[you fill in the rest]

The proper sequence to use depends on what you want to do, that is, what overall algorithm the traversal is part of.

 

[gfd43tg]

Okay, well I wrote a recursive function to find the fibonacci number of the $n^{th}$ term in the sequence as the input to the function with the formula for the fibonacci number given as

$F_{n} = F_{n-1} + F_{n-2}$ with the base case $F_{1} = 1$ and $F_{2} = 1$

function fibonacci_number = fibnum(n)
if n < 1
    return;
elseif n == 1 || n == 2
    fibonacci_number = 1;
else
    fibonacci_number = fibnum(n-1) + fibnum(n-2);
end

How do I decipher this to determine the order of traversal taken, or even how this recursive tree will appear? I turned on the breakpoint and am trying to follow it step by step, but it just isn't making sense to me. This could be in part due to an incomplete understanding of how the green and white arrows are interacting, and how the green arrow pointing down means.

What if I flipped my sum to be fibnum(n-2) + fibnum(n-1)?? Is the first term of the summation the left child of the root node? And it's sibling the right side.

EDIT: Just discovered that it matters very much indeed. I had it the other way around, so it wasn't calling in the order that my lecture slides indicated, because they had the sum flipped around. Very interesting...But can I manipulate this code to follow a post-order or in-order.

I did the breakpoint and ran the code step by step, and I see how it is recursively calling, however, I don't see how it is returning the calls.

Here is the updated code

function fibonacci_number = fibnum(n)
if n > 2
    fibonacci_number = fibnum(n-2) + fibnum(n-1);
else
    fibonacci_number = 1;
end