Converting recursive algorithms to tail recursive algorithms...??? 
Author Message
 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)))))



Sun, 20 Aug 1995 06:46:17 GMT  
 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)))))
                  ^

hard to do since i don't understand what + applied to a function
means.

i think you dropped a paren just before q.



Sun, 20 Aug 1995 06:00:02 GMT  
 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



Sun, 20 Aug 1995 22:47:08 GMT  
 Converting recursive algorithms to tail recursive algorithms...???

Quote:


>>            I was wondering, does anyone know how to convert the following
>>   algorithm to a tail recursive algorithm?:  Thanks in advance.

>>   (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.

Nonsense.  This function can be made completely tail-recursive.  True,
the bifurcation Mike mentions forces one to keep additional state, which
in a completely tail-recursive function would have to be kept in the
heap.  It's easier to resort to full recursion for that portion of the
computation and let the control stack maintain that state.

Nevertheless, partial tail-recursion is indeed possible.  If this didn't
look suspiciously like a homework problem, I'd post a possibility.   It
wouldn't be unreasonable to hint, though, that the state being kept by
the recursion is simply a number to be added to the result of the
recursive call.  The tail-recursive version simply needs to include that
number in the tail-recursive call.

Note that Mike's comments about memoization should be heeded.

                - Patrick A. O'Donnell



Mon, 21 Aug 1995 00:35:00 GMT  
 Converting recursive algorithms to tail recursive algorithms...???

(wiping egg off my face; *sigh*)


assuredly *not* nCm. My apologies for so elemental an error.

I *believe* the rest of my comments still hold (but *that* could be
wrong as well...)

--

                                ____/|
Michael Haynie                  \ o.O|   ACK!

                                   U



Mon, 21 Aug 1995 05:38:05 GMT  
 Converting recursive algorithms to tail recursive algorithms...???

In the hope that Conrad and others will find this useful, here is a
short example (Using Common LISP) of memoization used in a function to
compute combinations of N things K at a time.

--------------------->8-----------------------------------

;;; The following variables and functions constitute a memory for the
;;; COMB function. We use these items to ``memoize'' the results of a
;;; call to COMB with a particular N and K.
(defvar *combination-memo* (make-hash-table :test #'equal))

(defun combination-memo (i j)
  (gethash (list i j) *combination-memo*))

(defun setf-combination-memo (i j val)
  (setf (gethash (list i j) *combination-memo*)
        val))

(defsetf combination-memo setf-combination-memo)

(defun comb (n k)
  (declare (fixnum n k))
  (cond ((combination-memo n k))
        ((or (= k 0) (= n k))
         (setf (combination-memo n k) 1))
        (t (setf (combination-memo n k)
                 (+ (comb (- n 1) k)
                    (comb (- n 1) (- k 1)))))))

--------------------->8-----------------------------------

For your hacking pleasure.

--

                                ____/|
Michael Haynie                  \ o.O|   ACK!

                                   U



Tue, 22 Aug 1995 02:31:07 GMT  
 Converting recursive algorithms to tail recursive algorithms...???

Quote:

>;;; The following variables and functions constitute a memory for the
>;;; COMB function. We use these items to ``memoize'' the results of a
>;;; call to COMB with a particular N and K.

>(defvar *combination-memo* (make-hash-table :test #'equal))

>(defun combination-memo (i j)
>  (gethash (list i j) *combination-memo*))

>(defun setf-combination-memo (i j val)
>  (setf (gethash (list i j) *combination-memo*)
>    val))

>(defsetf combination-memo setf-combination-memo)

>(defun comb (n k)
>  (declare (fixnum n k))
>  (cond ((combination-memo n k))
>    ((or (= k 0) (= n k))
>     (setf (combination-memo n k) 1))
>    (t (setf (combination-memo n k)
>             (+ (comb (- n 1) k)
>                (comb (- n 1) (- k 1)))))))

Ah, but wouldn't it be so much nicer to write this? :-)

(defun-memoizing comb :test #'eql (n k)
   (declare (fixnum n k))
   (if (or (= k 0) (= n k))
        1
        (+ (comb (- n 1) k) (comb (- n 1) (- k 1)))))

- Josh :-)



Tue, 22 Aug 1995 04:46:41 GMT  
 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.
: >>
: >>   (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.
:
: Nonsense.  This function can be made completely tail-recursive.  True,
: the bifurcation Mike mentions forces one to keep additional state, which
: in a completely tail-recursive function would have to be kept in the
: heap.  It's easier to resort to full recursion for that portion of the
: computation and let the control stack maintain that state.
:
It is a standard fact that any function can be made completely tail-recursive
by converting it to CPS form.  See "Essentials of Programming Languages"
by Daniel P. Friedman et al, Section 8.4.

Each function (f x) is replaced by one with an extra continuation parameter
(f x k).  A bifurcating expression such as (+ (f x) (f y)) is converted to
(f x (lambda (v) (f y (lambda) (w) (k (+ v w)))))).

--
--Bill Kinnersley

226 Transfer complete.



Thu, 24 Aug 1995 20:50:54 GMT  
 
 [ 10 post ] 

 Relevant Pages 

1. Recursive to tail recursive definitions...???

2. head recursive or tail recursive

3. algorithm for type checking recursive types

4. Recursive Algorithm again

5. problems with recursive algorithm for dynamic time warping

6. Recursive algorithm to calculate Erlang-B tables

7. Recursive Algorithm getting stuck (because of Python Limits?)

8. Recursive algorithms anyone?

9. Recursive or quasi-recursive calls

10. Making things tail-recursive...

11. Why Not Tail-Recursive?

12. eliminating tail recursion in a recursive-descent evaluator?

 

 
Powered by phpBB® Forum Software