CODEWITHSUNDEEP
c#recursiontreebinary-treetraversal
Brist
Brist

Reputation: 19

How does double recursion work in a tree traversal function?

I've seen code for a binary tree traversal function, and saw it was using double recursion:

       public static void PrintTree(BinNode<int> t)
        {
            if (t != null)
            {
                Console.WriteLine(t.GetValue());
                PrintTree(t.GetLeft());
                PrintTree(t.GetRight());
            }
        }

What I don't understand is what C# does first - does it do both recursions at once, or does it do the first and then 'saves' the other, and if so when does it switch to other ?- there is only one exit statement and it also exits the second recursion(PrintTree(t.GetRight());) so how exactly does it get called?

Upvotes: 1

Views: 134

Answers (1)

Will Ness
Will Ness

Reputation: 71099

(I started writing this as a comment, hence the lack of capitalization. apologies for that; edits are welcome)

you just call a function, any function. it doesn't matter what it's name is. whether it is the same recipe or not. let the language implementers care about that. you just call it. it does what it ought to, according to the recipe (its code).

in other words: a function code is the recipe for what a function invocation ought to do. will do, when it is called. each invocation is a separate thing, a thing in itself. all invocations of the same function will follow the same recipe i.e. that function's code, working with the arguments they receive -- each invocation getting its own arguments.

then, the question whether they work at the same time or one after another, is a very good question. and the answer is, it depends on the language. I guess C# is a regular sequential language, so it'll call one function, let it do its thing, and when it's done the control returns to the caller and the next instruction in its recipe is performed.

and if that instruction is to make yet another function call, then it will be done.

Upvotes: 0

Related Questions