2. Decompose the problem Solve a problem by 1. solve a smaller instance (using wishful thinking) 2. convert the smaller solutions to the desired solution Step 2 requires creativity Must design the strategy before coding n!=n(n-1)(n-2)…=n[(n-1)(n2).]=n*(n-1)! solve the smaller instance, multiply it by n to get solution (define fact lambda(n)( n (fact(n 1)) sept.8.2003 16.41016.413 Intro to Scheme 3. Identify non-decomposable problems Decomposing not enough by itself Must identify the"smallest"problems and solve directly. AKa the base case Define 1!=1 (define fact lambda( if(=n1)1 (*n(fact(-n1))) sept.8,2003 16.41016.413 Intro. to scheme 8/ 2. Decompose the problem 1. solve a smaller instance (using wishful thinking) 2. creativity! design the strategy before coding. (n-1)! – (define fact convert the smaller solutions to the desired solution – n! = n(n-1)(n-2)... = n[(n-1)(n-2)...] = n * solve the smaller instance, multiply it by n to get solution Sept. 8, 2003 16.410 16.413 Intro. to Scheme 15 • Solve a problem by • Step 2 requires – Must (lambda (n) (* n (fact (- n 1))))) / 3. Identify non-decomposable problems • by itself and solve directly. • ( ) ( ( Decomposing not enough identify the "smallest" problems Define 1! = 1 = n 1 16 ) 1 Sept. 8, 2003 16.410 16.413 Intro. to Scheme • Must AKA “the base case”. define fact (lambda (n (if * n (fact (- n 1))))) 8