COMPSCI 1JC3 Lecture Notes - Lecture 5: Alonzo Church, Linear Search, Natural Number
11 Jun 2018
School
Department
Course
Professor
Recursion #5
- Recursion is a method of defining something in terms of itself
o Most fundamental ideas of computing
o An alternative to iteration
o Can make some programs easier to write
- All programming languages functions can be defined by recursion.
- Use of recursion requires care and understanding
o Recursive definitions can be nonsensical
o Sloppy use can lead to confusion
o Correctness is proved by induction
How does recursion work?
- Simplest instances are solved directly
- Other instances are broken down into smaller simpler instances until smallest is solved,
and solved from there
- This recursion uses the divide and conquer strategy
How does recursion work with functions?
- In the typical recursive definition of a function
o An instance if the problem is a set of inputs for the function
o Each instance / is assigned a natural number
o An instance / is a simple instance if n = 0
o A istace /’ is siple tha a istace / if /’ < or = /
- A recursive definition of a function is nonsensical if some instance / is reduced to an
istace /’ such that /’ is ot sipler tha /
*reverse1 :: Eq a => because a can be anything
- The natural numbers are Noetherian i.e there are an infinite descending sequences of
natural numbers.
- Ghcis default stack size is 512M
o Sigma Sum
▪ Sigma Sum m n f
▪ M> n = o , m<= n = sigmasum m (n-1) f + f n
▪ Sigmasum 1 3 id
▪ Sigmasum 1 2 + id3
▪ Sigmasum 1 1 + id 2 + id 3
▪ 6 = 1+ 2 + 3
o Application of sigmasum
▪ Alonzo church
▪ Sigmasum 1 100 (\x -> x) == 5050
▪ Sigmasum 1 4 factorial == 33
o Linear search
▪ linearSearch x L p
▪ :: a -> [a] -> (a-> a -> Bool) -> [a]
▪ linearSEarch _[]_ =[]
▪ linearSearch x (y:ys) p
▪ | p x y = [y]
find more resources at oneclass.com
find more resources at oneclass.com
