Transcript 4 + 3 + (2) + 1

Scheme : Definitions and Expressions
Scheme : Functions
(define (seven x)
(* x 7))
Scheme : Functions
(define (sum x y)
(+ x y))
Scheme : Conditionals (1)
(define (test x)
(cond ( (> x 0)1)
( (= x 0)0)
( (< x 0)-1)))
Scheme : Conditionals (2)
(define (test2 x)
(if (< x 0)(- x)
x))
Scheme : Recursion
sum the numbers 1 to N
(e,g, 1 to 4)
(define (sum n)
(if (= n 1)1
(+ n (sum(- n 1)))))
4+3+2+1
= 4 + (3 + 2 + 1)
= 4 + 3 + (2+1)
= 4 + 3 + (2) + 1
(sum 4) =
4 + (sum 3) =
Scheme : Recursion : The Factorial Function (1)
How many ways can you get n people to sit in n chairs ?
n = 3. (A,B,C)
n = 4. (A,B,C,D)
I lost the number of my new mobile phone
How can I find the number ? Get my girlfriend to phone
every single mobile number. (OK I’ll cook supper!)
Approximate solution: Say a mobile number has 10 digits
(actually 11) and each digit can be 0 – 9 (10 possibilitities).
So the solution is 10! How long will this take? Calculatore!
Scheme : Recursion : The Factorial Function (2)
(define (fact n)
(if (= n 1)1
(* n (fact (- n 1)))))
I lost the number of my new mobile phone
How can I find the number ? Get my girlfriend to phone
every single mobile number. (OK I’ll cook supper!)
Approximate solution: Say a mobile number has 10 digits
(actually 11) and each digit can be 0 – 9 (10 possibilitities).
So the solution is 10! How long will this take? Calculatore!
(fact 10)
Functional Recursion // Imperative Iteration
(define (fact n)
(if (= n 1)1
(* n (fact (- n 1)))))
Fundamental Principles of Recursion
A recursive function must call a simplified version of itself.
This is guaranteed to “bottom out” (to halt). Any call to itself
would produce an infinite regress.
Don’t run this … ah go on then ..
(define (factsr n)
(if (= n 1)1
(* n (factsr n))))
... and wait for the error message ... or worse