# Functional Programming - Recursion

67 %
33 %
Information about Functional Programming - Recursion
Education

Published on February 20, 2014

Author: uyar

Source: slideshare.net

## Description

Recursion, tail recursion.

Functional Programming Recursion H. Turgut Uyar 2013-2014

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Inﬁx Functions function calls can be written in inﬁx notation within backquotes example: the mod function even1 :: Integer -> Bool even1 n = mod n 2 == 0 -- OR: even1 :: Integer -> Bool even1 n = n `mod` 2 == 0

Preﬁx Operators operator calls can be written in preﬁx notation within parentheses example: the * operator even2 :: Integer -> Bool even2 n = (n `div` 2 ) * 2 == n -- OR: even2 :: Integer -> Bool even2 n = (*) (div n 2) 2 == n -- OR: even2 :: Integer -> Bool even2 n = (==) ((*) (div n 2) 2) n

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Guards writing conditional expressions can become complicated guards: Boolean expressions to check cases in function deﬁnitions function result is the expression for the ﬁrst valid guard name :: t1 -> t2 -> ... -> tk -> t name x1 x2 ... xk | g1 = e1 | g2 = e2 ... | otherwise = e

Guard Example maxThree :: Integer -> Integer -> Integer -> Integer maxThree x y z | x >= y && x >= z = x | y >= z = y | otherwise = z

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Errors an exception can be raised using error example: reciprocal (multiplicative inverse) reciprocal :: Float -> Float reciprocal x | x == 0 = error "zero does not have a reciprocal" | otherwise = 1.0 / x

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Recursion Examples consider two classic examples: greatest common divisor gcd’ :: Integer -> Integer -> Integer gcd’ x y = if y == 0 then x else gcd’ y (x `mod` y) factorial fact :: Integer -> Integer fact n | n < 0 = error "negative parameter" | n == 0 = 1 | otherwise = n * fact (n - 1)

Recursion Examples consider two classic examples: greatest common divisor gcd’ :: Integer -> Integer -> Integer gcd’ x y = if y == 0 then x else gcd’ y (x `mod` y) factorial fact :: Integer -> Integer fact n | n < 0 = error "negative parameter" | n == 0 = 1 | otherwise = n * fact (n - 1)

Stack Frame Example gcd’ x y = if y == 0 then x else gcd’ y (x `mod` y) gcd' 9702 945 |- gcd' 945 252 |- gcd' 252 189 |- gcd' 189 63 |- gcd' 63 0 63 63 63 63 63

Stack Frame Example gcd’ x y = if y == 0 then x else gcd’ y (x `mod` y) gcd' 9702 945 |- gcd' 945 252 |- gcd' 252 189 |- gcd' 189 63 |- gcd' 63 0 63 63 63 63 63

Stack Frame Example fact n | n < 0 = error "negative parameter" | n == 0 = 1 | otherwise = n * fact (n - 1) fact 4 |- 4 * fact 3 |- 3 * fact 2 |- 2 * fact 1 |- 1 * fact 0 1 1 2 6 24

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Tail Recursion if the result of the recursive call is also the result of the caller, then the function is said to be tail recursive the recursive function call is the last action: nothing left for the caller to do no need to keep the stack frame around → reuse the frame of the caller

Tail Recursion if the result of the recursive call is also the result of the caller, then the function is said to be tail recursive the recursive function call is the last action: nothing left for the caller to do no need to keep the stack frame around → reuse the frame of the caller

Stack Frame Example gcd’ x y = if y == 0 then x else gcd’ y (x `mod` y) gcd' 9702 945 gcd' 945 252 gcd' 252 189 gcd' 189 63 gcd' 63 0 63

Tail Recursion to rearrange a function to be tail recursive: deﬁne a helper function that takes an accumulator base case: return accumulator recursive case: make recursive call with new accumulator value

Tail Recursion Example factIter :: Integer -> Integer -> Integer factIter acc n | n < 0 = error "negative parameter" | n == 0 = acc | otherwise = factIter (acc * n) (n - 1) fact’ :: Integer -> Integer fact’ n = factIter 1 n

Stack Frame Example factIter acc n | n < 0 = error "negative parameter" | n == 0 = acc | otherwise = factIter (acc * n) (n - 1) fact 4 |- factIter 1 4 |- factIter 4 3 |- factIter 12 2 |- factIter 24 1 |- factIter 24 0 24 24

Tail Recursion Example the helper function doesn’t need to be visible fact’ :: Integer -> Integer fact’ n = factIter 1 n where factIter :: Integer -> Integer -> Integer factIter acc n’ | n’ < 0 = error "negative parameter" | n’ == 0 = acc | otherwise = factIter (acc * n’) (n’ - 1)

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Tree Recursion another classic example: the Fibonacci sequence ﬁbn =    1 if n = 1 1 if n = 2 ﬁbn−2 + ﬁbn−1 if n > 2 fib :: Integer -> Integer fib n | n == 1 = 1 | n == 2 = 1 | otherwise = fib (n - 2) + fib (n - 1)

Stack Frame Example fib 5 | ------------------ | | fib 3 fib 4 | | ------------- ------------- | | | | fib 1 fib 2 fib 2 fib 3 | ------------- | | fib 1 fib 2

Topics 1 Functions Inﬁx and Preﬁx Notations Guards Errors 2 Recursion Primitive Recursion Tail Recursion Tree Recursion Examples

Recursion Example exponentiation compute xy where y ∈ N pow :: Integer -> Integer -> Integer pow x y | y == 0 = 1 | otherwise = x * pow x (y - 1) let’s use the following: xy =    1 if y = 0 (xy/2) 2 if y is even x · xy−1 if y is odd

Recursion Example exponentiation compute xy where y ∈ N pow :: Integer -> Integer -> Integer pow x y | y == 0 = 1 | otherwise = x * pow x (y - 1) let’s use the following: xy =    1 if y = 0 (xy/2) 2 if y is even x · xy−1 if y is odd

Recursion Example fast exponentiation fastPow :: Integer -> Integer -> Integer fastPow x y | y == 0 = 1 | even y = sqr (fastPow x (y `div` 2)) | otherwise = x * fastPow x (y - 1) where sqr :: Integer -> Integer sqr n = n * n

Recursion Example square roots with Newton’s method start with an initial guess y (say y = 1) repeatedly improve the guess by taking the mean of y and x/y until the guess is good enough ( √ x · √ x = x) y x/y next guess 1 2 / 1 = 2 1.5 1.5 2 / 1.5 = 1.333 1.4167 1.4167 2 / 1.4167 = 1.4118 1.4142 1.4142 ... ...

Recursion Example goal: guess = √ x if guess is good enough: |guess · guess − x| < check whether the guess is good enough isGoodEnough :: Float -> Float -> Bool isGoodEnough guess x = abs (guess * guess - x) < 0.001 improve the guess improve :: Float -> Float -> Float improve guess x = (guess + (x / guess)) / 2.0

Recursion Example goal: guess = √ x if guess is good enough: |guess · guess − x| < check whether the guess is good enough isGoodEnough :: Float -> Float -> Bool isGoodEnough guess x = abs (guess * guess - x) < 0.001 improve the guess improve :: Float -> Float -> Float improve guess x = (guess + (x / guess)) / 2.0

Recursion Example goal: guess = √ x if guess is good enough: |guess · guess − x| < check whether the guess is good enough isGoodEnough :: Float -> Float -> Bool isGoodEnough guess x = abs (guess * guess - x) < 0.001 improve the guess improve :: Float -> Float -> Float improve guess x = (guess + (x / guess)) / 2.0

Recursion Example iterative computation newtonIter :: Float -> Float -> Float newtonIter guess x = if isGoodEnough guess x then guess else newtonIter (improve guess x) x newton :: Float -> Float newton x = newtonIter 1.0 x

Recursion Example newton :: Float -> Float newton x = newtonIter 1.0 x where isGoodEnough :: Float -> Float -> Bool isGoodEnough guess x’ = abs (guess * guess - x’) < 0.001 improve :: Float -> Float -> Float improve guess x’ = (guess + (x’ / guess)) / 2.0 newtonIter :: Float -> Float -> Float newtonIter guess x’ = if isGoodEnough guess x’ then guess else newtonIter (improve guess x’) x’

Recursion Example doesn’t work with too small and too large numbers (why?) isGoodEnough guess x’ = (abs (guess * guess - x’)) / x’ < 0.001

Recursion Example doesn’t work with too small and too large numbers (why?) isGoodEnough guess x’ = (abs (guess * guess - x’)) / x’ < 0.001

Recursion Example no need to pass x around, it’s already in scope newton x = newtonIter 1.0 where isGoodEnough :: Float -> Bool isGoodEnough guess = (abs (guess * guess - x)) / x < 0.001 improve :: Float -> Float improve guess = (guess + (x / guess)) / 2.0 newtonIter :: Float -> Float newtonIter guess = if isGoodEnough guess then guess else newtonIter (improve guess)

Recursion Example no need to pass x around, it’s already in scope newton x = newtonIter 1.0 where isGoodEnough :: Float -> Bool isGoodEnough guess = (abs (guess * guess - x)) / x < 0.001 improve :: Float -> Float improve guess = (guess + (x / guess)) / 2.0 newtonIter :: Float -> Float newtonIter guess = if isGoodEnough guess then guess else newtonIter (improve guess)

References Required Reading: Thompson Chapter 3: Basic types and deﬁnitions Chapter 4: Designing and writing programs

 User name: Comment:

August 23, 2017

August 23, 2017

August 23, 2017

August 23, 2017

August 23, 2017

August 23, 2017

## Related pages

Functional programming is a style of programming which ... 1 What is functional programming? 2 Functional vs ... of a list without using loops or recursion:

### Functional programming - Wikipedia, the free encyclopedia

Functional programming limited to well-founded recursion with a few other constraints is called ... Functional programming in non-functional ...

### scala - Functional Programming - Lots of emphasis on ...

Functional Programming - Lots of emphasis on recursion, ... Can someone please enlighten me why recursion is so important to functional programming paradigm?

### Functional Programming - 8. Tail Recursion

Tail recursion is significant, because any tail-recursive program can be written as a loop. 8.2 Converting to tail-recursive form Every function that is ...

### f# - functional programming with less recursion? - Stack ...

I am currently doing reasonably well in functional programming using F#. I tend, however, to do a lot of programming using recursion, when it seems that ...

### Understanding recursion in functional JavaScript programming

The problem. In JavaScript, if a function calls itself recursively then the JavaScript engine has to create what's called a new 'stack'. A stack is a chunk ...

### Are functional languages better at recursion ...

Are functional languages better at recursion? ... perhaps because most beginners to functional programming have used recursion before in imperative ...