Converting recursive algorithms to tail recursive algorithms...???

I was wondering, does anyone know how to convert the following

algorithm to a tail recursive algorithm?: Thanks in advance.

-Conrad

-------------------------------- CUT HERE ----------------------------------

(define (q m n)

(cond ((= m 1) 1)

((= n 1) 1)

((< m n) (q m m))

((= m n) (+ 1 (q m (- m 1))))

(#t (+ q m (- n 1)) (q (- m n) n)))))

Perhaps I am blind, but I do not think that tail recursion is possible

here. If I am not mistaken, q is the combinations of n things taken m

at a time, sometimes written C(n,m). The #t case above is the culprit,

as it bifurcates.

You may find a memoization technique helpful here, since this function

is quite expensive to compute, and each unique (m,n) has a unique

result.

1. define a data structure that uses the argument tuple as a key, such

that lookup using that key returns the correct function value for

the argument tuple. A hash table works well here.

2. Before attempting to *compute* a result, first check to see if the

result is stored. If so, use it.

3. If the result is not stored (memoized), then compute it recursively

using the memoizing function such that each recursive call will

also be able to memoize its results. This has the effect of

preventing muptiple recomputation for the same (m,n).

This will reduce computation time to a small constant over the long

run, and will greatly reduce the initial cost.

I would post an example, but I see that you are using scheme (yes?),

which I do not grok fully. However this works quite well in Common

LISP.

Further, there is an C(m,n) reduction that could save space; C(m,n) ==

C(m,m - n)

Hope this helps.

--

____/|

Michael Haynie \ o.O| ACK!

U