[racket] what's wrong with my code?

On Sun, Jan 20, 2013 at 6:50 PM, Robert Hume <rhume55 at gmail.com> wrote:
> I'm really stuck trying to figure this out.  Any pointers are useful!
> Here's the problem:
>
> f(n) = n if n<4
> and
> f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) + 4f(n - 4) if n>= 4
>
> Here's my solution so far -- any one know what I'm doing wrong?
>
> (define (f n)
>
>   (define (f-iter result i)

Hi Robert,

Strong recommendation: try writing f just in terms of itself, not in
terms of f-iter.  First get it right, mathematically speaking, and
then you may be in a better position to make it efficient.

---

Once you have a correct version, maybe you want it to go fast.  :)

Shriram wrote a blog post about dynamic programming and memoization
that may be helpful:

    http://blog.racket-lang.org/2012/08/dynamic-programming-versus-memoization.html

If you write a correct definition first, and then memoize, you'll get
an efficient implementation which should be very readable.  Try that
first.

As an example of the memoization approach, also see:

    http://blog.racket-lang.org/2012/10/the-3n1-problem_4990.html

and look at how the define/memo stuff is used to accelerate the function.

---

If you must make it iterative: I see you're trying to do some sort of
dynamic programming approach with f-iter, but you don't have enough
information in f-iter.  Your recurrence looks four steps behind, so
you'll probably need to keep four auxiliary variables to the values
for f(n-1), f(n-2), ... f(n-4) as you compute the recurrence.

I expect an approach similar to how iterative fibonacci number
computation works will apply here.