Functional Programming and Scheme
CMPSC 461
Programming Language Concepts Penn State University
Fall 2020
Recursion and Induction
Recursion
• Computationally: a procedure/function calls itself
• Semantically: defining a computation/value inductively
Induction
• Naturalnumber:i)0∈N ii)ifn∈N,then(n+1)∈N
• Inductive proof that property P holds on any n ∈ N :
• i) for 0, P holds
• ii)ifn∈NandPholdsonn,thenPholdson(n+1)∈N
2
Factorial
𝑛! = 𝑛∗ 𝑛−1 ∗⋯∗1
Inductive definition
• Factorial:
• i)0!=1
• ii) n! = 𝑛 ∗ 𝑛 − 1 !
(define (factorial n)
(if (= n 0) 1
(* n (factorial (- n 1)))))
3
Fibonacci Number
Numbers in the following sequence: 1 1 2 3 5 8 13 21 …
Inductive definition
• fib(1) = 1
• fib(2) = 1
• fib(n) = fib(n-1) + fib(n-2)
(define (fib n)
(cond ((= n 1) 1)
((= n 2) 1)
(else (+ (fib (- n 1)) (fib (- n 2))))))
4
List
A list is a sequence of expressions in parentheses
(1 2 3) (sqrt x) (x 1 “abc”)
Programs are just lists interpreted as code
A list is either
• Empty: ()
• or non-empty: it has a head and a tail, where
the head can have any type the tail is itself a list
Inductive definition!
5
List Construction
Inductive definition
• ()isalist
• Ifeis an expression,xsis a list,(cons e xs) is a list
“cons” is a built-in function for constructing lists
(1 2 3 4) is equivalent to
(cons 1 (cons 2 (cons 3 (cons 4 ‘()))))
head tail
6
List Destruction
car and cdr are the destructors for lists: if xs is a non-empty list, then
(car xs) is the head
(cdr xs) is the tail
Algebraically:
(car (cons x xs)) = x (cdr (cons x xs)) = xs
7
List Destruction
(car ’(1 2 3)) = 1, which is the same as
(car (cons 1 ’(2 3)))) = 1
(cdr ’(1 2 3)) = (2 3), which is the same as (cdr (cons 1 ’(2 3)))) = (2 3)
8
List
(1 2 3) (sqrt x) (x 1 “abc”)
“cons” adds an element to a list “car” returns the head of a list
“cdr” returns the tail of a list “append” concatenates two lists
append ’(1 2 3) ’(4 5 6)
9
Additional List Functions list creates a list from its arguments
(list 1 2 3)
null? checks if a list is empty
list? checks whether something is a list
cadr the second item in a list caar, cdar, cddr …
10
List Example
Define lstSum, which returns the sum of a num list
Inductive definition i) ‘(): 0
ii) (cons head tail): head + lstSum(tail)
(define (lstSum lst)
(if (null? lst) 0
(+ (car lst) (lstSum (cdr lst)))))
11
Recursion Over Lists
(define (f l)
(if (null? l) (base-case)
(recursive-case, using (car l),(cdr l))))
12
Equality Test
equal: return #t if two expressions have the same structure and content
(equal? 1 1)
(equal? ’(1 2) ’(1 2))
(equal? 5 ’(5))
(equal? ’(1 2 3) ’(1 (2 3)))
(equal? ’(1 2) ’(2 1))
13
List Example
Define subs, which takes a b l, and replaces a with b in l
(define (subs a b l)
(if (null? l) ‘()
(let ((rest (subs a b (cdr l))))
(if (equal? (car l) a)
(cons b rest)
(cons (car l) rest)))))
14