I'm currently learning about recursion in Scheme. I found this recursive definition but I don't understand what it is trying to do. If someone could explain it to me, I would appreciate it. Here is the definition:
(define (function ls)
(if (null? ls) '()
(append
(map (lambda (x) (cons (car ls) x))
(function (cdr ls))
)
(function (cdr ls))
)
)
)
In its current state, function
simply returns the empty list, no matter the input. However, it does ring a bell. It looks like a failed attempt to implement the powerset
function:
(define (powerset ls)
(if (null? ls)
'(())
(append (map (lambda (x) (cons (car ls) x))
(powerset (cdr ls)))
(powerset (cdr ls)))))
Can you spot the difference? the base case in your code is wrong! In case you were wondering, powerset
returns the set of all possible subsets of a list:
(powerset '(1 2 3))
=> '((1 2 3) (1 2) (1 3) (1) (2 3) (2) (3) ())