2009-06-03

Post date: Jun 3, 2009 7:07:19 PM

Went over sample midterm questions posted here. Some suggestions:

Tail recursion is preferred when scanning a list left-to-right, and the result does not specify a particular order. If the result must be in the same order as input, then non-tail is easier to implement. If tail-recursion is desired and result must be in the same order as input, then the accumulator, which is constructed by prepending elements from left-to-right, needs to be reversed. Do not use list append, as it is O(n) for each element, which makes the whole function O(n²).
When traversing the whole binary tree, tail recursion is still possible, but we need to use continuation passing style. For example, in post-order traversal, when traversing the left subtree, we pass it a continuation to tell it what to do when that's done (i.e. should traverse the right tree). When traversing the right tree, we pass it a continuation to tell what to do when that's done (i.e. do something with the parent). A continuation is a function closure that is called by the base case of recursion, taking the accumulator (which is the partial result) as the argument. The continuation would perform further computation on the accumulator.
When tackling postbal problem, the function itself is too restricted to be called recursively: suppose length(xs) = 2^h - 1, postbal(xs, h) = t returns balanced tree t such that postord(t) = xs. We want to divide xs into three parts, xs1, xs2, x_n, where lenght(xs1) = length(xs2) = (length(xs) - 1) / 2 = 2^h-1 - 1. A common strategy is to strengthen the recursion as follows: postbal_super(xs, h) = (t, xs') is like postbal(xs, h) except it only requires that length(xs) >= 2^h - 1. It will return the excessive parts of xs in xs'.