[plt-scheme] DrScheme crash, and my bad programming

Just to clarify, not all tail calls are tail recursive.

A tail call is just a procedure call just before the end of the procedure (see "Tail call - Wikipedia, the free encyclopedia" at http://en.wikipedia.org/wiki/Tail_call).  Tail recursion (see "Tail recursion - Wikipedia, the free encyclopedia" at http://en.wikipedia.org/wiki/Tail_recursion) is a special case of a tail call in which the procedure is calling itself.

Benjamin L. Russell

--- On Thu, 5/22/08, Chongkai Zhu <czhu at cs.utah.edu> wrote:

> I would suggest you to read more about *tail call*, or as
> some one put 
> it, tail recursion. Afterall, let loop is just a macro that
> expands to 
> recursive function call.
> 
> In the code you posted, the line
> 
>     [(solution6? a b c d n) (add1 (count-solutions a b c
> (add1 d) n))]
> 
> is not tail call. You didn't post the code that
> "break up the recursion 
> into one function that recurses on c and d while another
> recurses on a 
> and b", so I can't tell whether it is tail call or
> not.
> 
> Chongkai
> 
> Joshua Zucker wrote:
> > I know that there's probably a more conventional
> way to write code
> > like this -- this is just my dorky translation of a C
> for loop into a
> > recursion.
> >
> > (define (solution6? a b c d n)
> >   (let ([f (- (* 12 n (- n 2)) b (* 3 c) (* 2 d))])
> >     (and (>= f 0)
> >          (>= (* n n n) (+ a b c d (- (* 8 n) (* 2
> a) b) f)))))
> >
> > (define (count-solutions a b c d n)
> >   (cond
> >     [(> a (* 4 n)) 0]
> >     [(> b (- (* 8 n) (* 2 a))) (count-solutions
> (add1 a) 0 0 0 n)]
> >     [(> c (- (* 4 n (- n 2)) b)) (count-solutions a
> (add1 b) 0 0 n)]
> >     [(> d (quotient (- (* 12 n (- n 2))
> >                        b
> >                        (* 3 c))
> >                     2)) (count-solutions a b (add1 c)
> 0 n)]
> >     [(solution6? a b c d n) (add1 (count-solutions a b
> c (add1 d) n))]
> >     [else (count-solutions a b c (add1 d) n)]))
> >
> > But if you run (count-solutions 0 0 0 0 10) or so,
> > where the recursion is then going a couple hundred
> million layers deep,
> > DrScheme crashes.
> >
> > If I break up the recursion into one function that
> recurses on c and d
> > while another recurses on a and b, then it has no
> trouble.
> >
> > If you want me to be more specific about exactly what
> code I run to
> > make DrScheme crash, let me know.  (By crash, I mean
> the application
> > quits -- v372 on OS X 10.4)
> >
> > But I'm also writing because I figure there are
> more elegant ways to
> > write for-loop-esque code like this -- maybe I should
> post that to
> > plt-edu instead -- but I'd love to learn what the
> conventional way is
> > to write this type of code.  Something with let loop? 
> I've seen that
> > idiom but I don't really get it.
> >
> > Finally, the algorithm here is just brute-force
> counting of solutions
> > to a system of three linear diophantine equations in
> seven variables,
> > where all the variables have to be nonnegative.  So I
> pick 4 of them,
> > look at all the possibilities, and check for whether
> the remaining
> > values are positive (with a few shortcuts, since the
> limits of the
> > loop guarantee some of them will be positive).  So
> maybe there are
> > much much much more efficient ways of counting the
> number of solutions
> > to a system like this?  (Equivalently, the number of
> lattice points in
> > a 7-dimensional region bounded by a bunch of
> hyperplanes.)
> >
> > Thanks!
> > --Joshua Zucker
> > _________________________________________________
> >   For list-related administrative tasks:
> >   http://list.cs.brown.edu/mailman/listinfo/plt-scheme
> >   
> _________________________________________________
>   For list-related administrative tasks:
>   http://list.cs.brown.edu/mailman/listinfo/plt-scheme