Exponential base change based on symmetry
Timothy J. Rolfe · ACM Inroads · 2011
This article examines the recurrence obtained for Catalan numbers based on their description of the number of unique binary search tree structures possible with n distinct keys. The straightforward recurrence obtained, when transformed into a recursive method, obtains the solution in 3 n method invocations. With a small change based on symmetry, this can be changed to obtain the solution in 2 n method invocations. Of course, one can obtain the solution in massively fewer operations (O( n 2 )) in a dynamic programming/memoized solution.