Information about Functional Programming - Recursion

Recursion, tail recursion.

License © 2013-2014 H. Turgut Uyar You are free to: Share – copy and redistribute the material in any medium or format Adapt – remix, transform, and build upon the material Under the following terms: Attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. NonCommercial – You may not use the material for commercial purposes. ShareAlike – If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original. For more information: https://creativecommons.org/licenses/by-nc-sa/4.0/ Read the full license: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode

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

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

Read more

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

Read more

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

Read more

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 ...

Read more

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 ...

Read more

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 ...

Read more

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

Read more

In this video, we are going to learn about recursion - what recursion is, how it works, and why it's useful. This video is part of a series ...

Read more

Performance: recursion vs. iteration in Javascript. ... Browse other questions tagged javascript functional-programming recursion or ask your own question.

Read more

## Add a comment