;; The first three lines of this file were inserted by DrRacket. They record metadata ;; about the language level of this file in a form that our tools can easily process. #reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname fib) (read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-decimal #f #t none #f ()))) ;; DEMO: Fibonacci numbers ;; a Positive is ;; -- 0 ;; -- (+ Positive 1) 0 (+ 2 1) (+ 0 1) ;; fib: Positive -> Positive ;; fib: computes the Fibonacci number indexed by the given number ;; (fib 0) ==> 1 ;; (fib 1) ==> 1 ;; (fib 10) ==> 55 ;;structural template #;(define (fib i) (cond [(= i 0) (... i ...)] [else ( ... i ... ... (- i 1) ... ... (fib (- i 1)) ...)])) ;;generative template (revisited) #;(define (fib i) (cond [(trivially-solvable-1? i) (determine-solution-1 i)] ... [(trivially-solvable-n? i) (determine-solution-n i)] [else (combine ... i ... ... (fib (generate-problem-1 i)) ... ... (fib (generate-problem-n i)) ...)])) (define (fib i) (cond [(= i 0) 0] [(= i 1) 1] [else (+ (fib (- i 1)) (fib (- i 2)))])) ;; termination argument: each recursive call to fib consumes numbers smaller than 1 (check-expect (fib 0) 0) (check-expect (fib 1) 1) (check-expect (fib 10) 55) (fib -1)