 # FP101x - week 5 Recursive Functions

• factorial :: Int -> Int
• factorial n = product [1..n]
• factorial maps any integer n to the product of the integers between 1 and n
• ex)
``````factorial 4
= product [1..4]
= product [1,2,3,4]
= 1*2*3*4
``````

### Recursive Function

• functions can also be defined in terms of themselves
• factorial 0 = 1
• factorial n = n * factorial (n-1)
• ex)
``````factorial 3
= 3 * factorial 2
= 3 * ( 2 * factorial 1)
= 3 * ( 2 * ( 1 * factorial 0 ) )
= 3 * ( 2 * ( 1 * 1 ) )
= 3 * ( 2 * 1 )
= 3 * 2
= 6
``````

### why

• simpler to defined in terms of other functions.
• naturally be defined in terms of themselves
• simple but powerful mathematical technique of induction

### Recursion of Lists

• Recursion is not restricted to numbers, but can also be used to define functions on lists
``````product :: [Int] -> Int
product [] = 1
product (n:ns) = n * product ns
``````
• product maps the empty list to 1 and any non-empty list to its head multiplied by the product of its tail
``````product [2,3,4]
= 2 * product [3,4]
= 2 * ( 3 * product )
= 2 * ( 3 * ( 4 * product [] ) )
= 2 * ( 3 * ( 4 * 1 ) )
= 24
``````

ex ) function length

``````length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
``````
``````length [ 1 , 2 , 3 ]
= 1 + length [ 2 , 3 ]
= 1 + ( 1 + length [ 3 ] )
= 1 + ( 1 + ( 1 + length [ ] )
= 1 + ( 1 + ( 1 + ( 1 + 0 ) )
= 3
``````

ex ) reverse

``````reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
``````
``````reverse [1,2,3]
= reverse [2,3] ++ 
= ( reverse  ++  ) ++ 
= ( (reverse [] ++  ) ++  ) ++ 
= ( ([] ++  ) ++  ) ++ 
= [3,2,1]
``````
• appending the element from right to left

### Multiple Arguments

• zip
``````zip :: [a] -> [b] -> [(a,b)]
zip [] _ = []
zip _ [] = []
zip (x:xs) (y:ys) = (x,y) : zip xs ys
``````
• drop
``````drop :: Int -> [a] -> [a]
drop 0 xs = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
``````
• appending
``````(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys  = x : (xs ++ ys)
``````

### Quicksort

• rule 1 : The empty list is already sorted
• rule 2 : Non-empty lists can be sorted by sorting the tail values <= the head sorting the tail values > the head, and then appending the resulting list on either side of the head value
``````qsort :: [Int] -> [Int]
qsort [] = []
qsort ( x : xs ) =
sort smaller ++ [x] ++ sort larger
where
smaller = [ a | a <- xs, x <= x]
larger = [ b | b <- xs, b > x ]
``````
``````q [ 3,2,4,1,5 ]
q  [2,1] ++  ++ q [4,5]
q ++  ++ q[] ++  ++ q[] ++  ++ q
 ++  ++ [] ++  ++ [] ++  ++ 
``````
• produce a list with n identical elements
``````replicate :: Int -> a -> [a]
``````
• select the nth element of a list
``````(!!) :: [a] -> Int -> a
``````
• decide if a value is an element of a list
``````elem :: Eq a => a -> [a] -> Bool
``````