eharetea

Implementing tree recursion with Scheme.

Implementing tree recursion with Scheme, a dialect of Lisp.

Date Created:Thursday September 11th, 2008 02:54 PM
Date Modified:Tuesday January 19th, 2010 10:32 PM

This function takes a set of numbers and finds if there exists a subset or combination of the input set that adds up to the "n" variable passed into the function.

Using recursion, the n variable is passed into a recursive call twice: Once where n is passed in unmodified, and the other where we subtract it by the value of the first number in the list. If n = 0, then we know that elements within the set add up to zero since n - n = 0.

This function can be called like so:

(subset-sum '(1 2 3 4 5) 5)

(define (subset-sum s n)
  (cond ((< n 0) #f)
        ((= n 0) #t)
        ((empty? s) #f)
        (else
         (or
           (subset-sum (bf s) n)
           (subset-sum (bf s) (- n (first s)))
         )
        )
  )
)

            

Simple Tree Recursion by Dan Lynch
is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States License
Based on a work at www.3daet.com
Permissions beyond the scope of this license may be available at http://www.3daet.com