[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