As mentioned in the previous slog, I think recursion is a quite ingenious algorithm. By using its output as argument, it can solve many complicated function with only a few lines of code. Despite its comparably large O(n), it's still remarkable for its well-constructed idea of computing.
Professor Danny used the example of nested-list to introduce this clever algorithm. What should we do with a general nested-list to count it's depth/length, gather all items, sum up its elements or find the maximum value?
These cases was quite tricky even impossible for us to solve at that time. We need to use recursion for these problems.
Since recursive functions take in its output as its argument, it'll keep computing without a base case, which is the condition for it to jump out of calculating and return a basic result. Take nested-lists as an example, we use method "is_instance" to decide whether an object is a list. If the result is True then we simply implement our function on all of its item. We repeat this process until the base case (the item is no longer list) is reached.
Recursion has a very large range of application. It can be used to construct Fibonacci Sequence, visualize Collartz's problem or even realize AI (artificial intelligence). I think this is an algorithm with tremendous meaning and I am deeply impressed by its beauty.
No comments:
Post a Comment