recursionracketr5rs

Recursive Definitions


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))
        )
    )
)

Solution

  • 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) ())