Week 4 final lab

In the final lab of week4’s course, why this function build_tree_recursive is used inside its own definition, which means a function is called even before a function itself is finished defined?

Yes, that is the definition of a recursive function: a function that calls itself. This can be a useful technique for writing code that does things like traversing a tree, as in this case. You just have to be careful to limit the depth of the recursion, because the call stack gets deeper with each recursive call. You can see that the logic they give you does put a limit on the depth of the recursion.

Another famous example is generating Fibonacci numbers. The definition of Fibonacci numbers is naturally recursive and it’s very simple and clear to write the code in a recursive way. The problem is that the computational complexity of writing it that way is O(2^n), so it only works for relatively small values of n. It’s pretty easy to write a Fibonacci generator function just using loops instead of recursion that has complexity O(n).

You can learn more by googling “python recursive functions”.

Thanks for the comments. If the function is defined without the last two lines but add a for loop to repeat it, does it have the same effect as recursive function?

You could rewrite this function using loops and get the same net effect, but the loop would have to include essentially all the logic shown, not just the last two lines.

A simpler exercise to demonstrate how to implement an algorithm either with recursion or loops would be the Fibonacci example I mentioned above. If you are curious to explore these ideas further, that would be a good experiment to run.