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

 

[LudusRex]

The order of traversal in a recursive fibonacci function depends on how the function is implemented. However, the most common order of traversal is pre-order traversal, which means that the function first visits the parent node, then the left child, and then the right child.

To remember the three orders of traversal, you can use the mnemonic "PIL" - parent, left child, right child for pre-order traversal, "LPI" - left child, parent, right child for in-order traversal, and "LIR" - left child, right child, parent for post-order traversal.

There is no default order of traversal in a recursive program. The order depends on the specific problem and how the function is designed to solve it. The three different ways of traversing allow for different ways of analyzing and solving a problem.

Pre-order traversal is often used when we want to print the elements of a tree in a specific order, in-order traversal is useful for evaluating expressions in a binary tree, and post-order traversal is commonly used in deleting nodes from a tree. Each traversal method has its own unique advantages and uses.