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

Downloads:

Download: tree.scm 225 B

Please login or Click Here to register for downloads

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