listrecursionschemeracketsubtotal

# accumulative recursive function to produce a list of subtotals from last to first

Trying to do this `'(3 2 1)` -> `'(6 3 1)` with accumulative recursion I can get the result (sort of) that I desire, what I mean is that my firsts and rests seem to be in the right order but my `(cons` expects a list and I give it a number. Any help is appreciated.

If I replace `(cons` with `(list` in the helper and I `(reverse` the `li` variable in the function I get the `'(6 3 1)` that I would like but with `(list (list (list '()` in front. I would just like `'(6 3 1)`

This is what I have

``````(define (subtotal li)
(subtotal-help (reverse li) 0))

(define (subtotal-help li acc)
(cond
[(empty? li) empty]
[else
(list
(subtotal-help (rest li)
(+ (first li) acc))
(+ (first li) acc))]))
``````

Running `(subtotal li)` produces `'(((() 6) 3) 1)`, and with `cons` is produces `'(((() . 6) . 3) . 1)`. I need just `'(6 3 1)`.

Solution

• You should use `cons` to build an output list, not `list`. Your code is close to being correct, we just need to shuffle things around and add one extra `reverse` at the end:

``````(define (subtotal li)
(reverse
(subtotal-help (reverse li) 0)))

(define (subtotal-help li acc)
(cond
[(empty? li) empty]
[else (cons (+ (first li) acc)
(subtotal-help (rest li) (+ (first li) acc)))]))
``````

But if you really want a tail-recursive solution, then it takes a bit more of work:

``````(define (subtotal li)
(cond
[(empty? li) empty]
[else (let ((lst (reverse li)))
(subtotal-help (rest lst) (list (first lst))))]))

(define (subtotal-help li acc)
(cond
[(empty? li) acc]
[else (subtotal-help (rest li)
(cons (+ (first li) (first acc))
acc))]))
``````

Either way, it works as expected:

``````(subtotal '(3 2 1))
=> '(6 3 1)
``````