In the lab we worked on recursion methods that involved a tree which has its children in a list. A crucial aspect of mastering these types of trees is to know when to place items inside or outside the list comprehension square brackets.
Personally I feel like novice when trying to formulate these recursion functions, often relying on a bit of trial error via the interpreter. So far I've been using this visualization to better imagine recursion processes:
Additionally, it is useful to think of a very short 2 level tree to get a handle of what the base cases and recursive cases should be. The benefit is that you can easily see your program 'resolve' itself, or hit the base case with only one step. If your program works for this simplified example chances are it'll work for all other levels.
Other things to look out for are fringe base cases and being wary about nested lists. For the former problem, inputs like like empty trees or None require a special base case to handle them. Regarding nested lists I realized that I should be careful about using them as each recursive call combined with a list comprehension will produce a nested list each level that is returned. The way to get around this is to either use a helper function 'gather lists' which flattens a depth 2 list to a single level, or just not have base cases return list objects at all.
It's funny that these kinds of tips can't really be taught and appreciated without actually diving in to the programming.
In addition, another useful technique that I learned that helps with finding values to certain depth levels is to use a function that decrements depth each recursive call. For instance Call(tree, n - 1) paired up with a base case of 'if n == 0' would allow values at a desired depth to be manipulated.
No comments:
Post a Comment