From: Conrad Taylor
Subject: Converting recursive algorithms to tail recursive algorithms...???
Date:
Message-ID: <C3A9x6.Cz7@cs.uiuc.edu>
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)))))
In article <··········@cs.uiuc.edu> ·······@cs.uiuc.edu (Conrad Taylor) writes:
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.
In article <··········@cs.uiuc.edu> ·······@cs.uiuc.edu (Conrad Taylor) writes:
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!
···@wisdom.attmail.com =(_)= THPHTH!
U
(wiping egg off my face; *sigh*)
As ···@NMSU.Edu has kindly pointed out, the code in question is most
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!
···@wisdom.attmail.com =(_)= THPHTH!
U
From: Patrick A. O'Donnell
Subject: Re: Converting recursive algorithms to tail recursive algorithms...???
Date:
Message-ID: <1cmhy2wo4@sluggo.ai.mit.edu>
In article <················@wisdom.wisdom.attmail.com>, Mike Haynie writes:
>In article <··········@cs.uiuc.edu> ·······@cs.uiuc.edu (Conrad Taylor) writes:
>> 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
From: Bill Kinnersley
Subject: Re: Converting recursive algorithms to tail recursive algorithms...???
Date:
Message-ID: <C3Irov.Bt5@hawk.cs.ukans.edu>
In article <·········@sluggo.ai.mit.edu> ···@ai.mit.edu (Patrick A. O'Donnell) writes:
: In article <················@wisdom.wisdom.attmail.com>, Mike Haynie writes:
: >In article <··········@cs.uiuc.edu> ·······@cs.uiuc.edu (Conrad Taylor) writes:
: >> 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
·····@hawk.cs.ukans.edu
226 Transfer complete.
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!
···@wisdom.attmail.com =(_)= THPHTH!
U
From: Joshua M Yelon
Subject: Re: Memoization example [was Re: Converting ... to tail recursive algorithms]
Date:
Message-ID: <C3Dtpt.FxE@news.cso.uiuc.edu>
···@wisdom.attmail.com (Mike Haynie) writes:
>;;; 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 :-)