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