CODEWITHSUNDEEP
recursionscheme
Mutating Algorithm
Mutating Algorithm

Reputation: 2758

Recursion issue in Scheme

The Following Code:

(define (rcons val lst)
    (if (not (null? lst))
        (cons (car lst) (rcons val (cdr lst)))
        (cons lst (list val)))))

(rcons 'E '(A B C D))

Should produce (A B C D E) but instead gives a result of (A B C D () E)

What' wrong with my recursive step ?

Upvotes: 0

Views: 45

Answers (2)

Sylwester
Sylwester

Reputation: 48735

You are so close!

List structure is iterated from beginning to end and built from end to beginning. If you want to make the list (1 2 3) you first have to make (2 3) then cons the first 1 to the finished constructed list (2 3). Your rcons do that as you see (cons (car lst) (rcons val (cdr lst))) which makes a list with the current value to the rcons of the rest of the list. The cons is done after both expressions has been evaluated. So for a 3 element list it will recurse 3 times. (cons first-value (cons second-value (cons third-value (rcons val-value '()))))

So if val is 4 (rcons 4 '()) should produce (cons 4 '()) or just (list 4) which is the same. This should work nicely.

(define (rcons val lst)
    (if (not (null? lst))
        (cons (car lst) (rcons val (cdr lst)))
        (list val)))

(rcons 4 '())      ; ==> (4)
(rcons 4 '(1 2 3)) ; ==> (1 2 3 4)

Upvotes: 0

Reut Sharabani
Reut Sharabani

Reputation: 31339

I can't run this locally, but you should be returning the end of the list on the final recursion (and not the entire list like you're trying to do, which is always null there by the way...):

(define (rcons val lst)
    (if (not (null? lst))
        (cons (car lst) (rcons val (cdr lst)))
        (cons val '()))) ; recursion ends here - only return end of list cons

Remember proper lists end in null ('()).

List structure:

What you get if you think of the recursion unfolding is (look at the last cons):

(cons #1 (cons #2 (cons #3 (cons .... (cons val '()))))

#1, #2, #3 etc describe the members of the original lst as well as the frame number (1 being the first).

More visualising - the recursion unfolds:

; {x} - x marks frame as well as location in original 'lst'
; frame 1
(cons (car lst {1}) (rcons val (cdr lst)))
; frame 2
(cons (car lst {1}) (cons (car lst {2}) (rcons val (cdr lst))))
; frame 3 ...
(cons (car lst {1}) (cons (car lst {2}) (cons (car lst {3}) (rcons val (cdr lst)))))

If you look back at List structure, it's easy to see we want val to be the car of the last cons, and '() to be it's cdr - to form a proper list. This is exactly what I fixed in your code.

Upvotes: 2

Related Questions