CSC 148 Python Week 11 Slog: Revisit of the application of Recursion

This week, I am going to revisit my Week 7 slog talking about Recursion and its efficiency. I think I understand more about recursion especially after learning about Binary Tree Traversal and Efficiency. Also, I know more about the advantages and disadvantages of using recursion.

Recursion means "defining something in terms of itself”. The graph below I think can best describe the concept of recursion as it seems that it is always in a circle algorithm. Last time, I did not realize the broad applications and extensions of recursion. I only focused on its relationship with iterative loop as some of the problems will be solved more efficiently using recursion. After a few weeks, I find out its application in Tree traversal as there are many of the methods inside the tree algorithm require the use of recursion like "Insertion", "Binary Searching" and "Deletion". Also, in our assignment, we also use recursion when using "Depth First Search" and "Bread First Search". I believe recursion can be used in more fields and we will discover that in our future study.

However, in terms of "efficiency", we always find that recursion is not always efficient comparing with "iterative" methods. For example, in terms of writing "Fibonacci" algorithm, while using iterative method, it will only take O(n) time. However, if we use recursive method, we can see that it will take O(2 to the power of n) times. Also, recursive method takes larger memory than iterative method.

In summary, we can get the following conclusion. Sometimes a recursive method has more to do following a recursive call. It gets done only after the recursive call (and all calls it makes) finishes. In addition, recursion is often simple and elegant, but could be less efficient when we apply it to the wrong problem as it may also takes a lot longer time than iterative method. Thus, we need to consider whether using iterative method or using recursion when solving a problem!