[plt-scheme] DrScheme crash, and my bad programming
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
>