Linear recursion #

Definition. A recursive function/method is linear recursive if it performs at most one recursive call each time it is executed.

Hint. In an imperative language (like Java), a linear recursive algorithm can easily be transformed into an iterative one (i.e. an algorithm that uses only loops).

Haskell does not admit loops, so linear recursion is the standard way to perform simple iterations (although list comprehensions can be used instead in certain cases). Accordingly, in this section, we will mostly use Haskell as an illustration.

Execution #

Example. The following function sums a list of integers:

1 2 3

sum :: [Int] -> Int sum [] = 0 sum (x : xs) = x + sum xs

Let us clarify how an expression like sum [1,2,3] is evaluated.

Fist, recall that [1,2,3] is syntactic sugar for 1 : (2 : (3 : [])).

Therefore when the pattern (x : xs) (Line 3) is matched against [1,2,3]:

• x matches 1, and
• xs matches 2 : (3 : []) (or equivalently, [2,3])

So the evaluation of sum [1,2,3] performs a recursive call sum [2,3] (Line 3).

Besides, the + operation is performed after the recursive call.

So the following sequence of events takes place:

1. the evaluation of sum [1,2,3] starts
2. $\quad$ the evaluation of sum [2,3] starts
3. $\quad\quad$ the evaluation of sum [3] starts
4. $\quad\quad\quad$ the evaluation of sum [] starts
5. $\quad\quad\quad$ the evaluation of sum [] ends and returns 0
6. $\quad\quad$ the evaluation of sum [3] ends and returns 3 + sum [] (i.e. 3)
7. $\quad$ the evaluation of sum [2,3] ends and returns 2 + sum [3] (i.e. 5)
8. the evaluation of sum [1,2,3] end ands returns 1 + sum [2,3] (i.e. 6)

After Step 4, the call stack is:

sum []
sum [3] : 3
sum [2,3] : 3
sum [1,2,3] : 3
<rest of the stack>

Hint. Understanding the execution of a recursive program (as we did above) is mostly useful for debugging. In order to write a recursive program, one can very often use a simpler, high-level methodology, sketched immediately below.

Solving a problem recursively #

Hint. Recursion is often convenient to solve a problem (i.e. find an algorithm that performs a certain task), when the input is a collection or data structure: list, array, matrix, tree, graph, etc.

Methodology. To solve a problem recursively:

• (Base case). If the input $I$ is minimal (e.g. of size 0 or size 1), then solve the problem directly.
• (Inductive case). Otherwise:
  1. Within $I$, identify one or several candidate smaller input(s) $I_1$, .., $I_k$.
  2. Solve the problem for each $I_1$, .., $I_k$ by performing recursive calls.
  3. Use the results(s) of the recursive calls to solve the problem for $I$.

In other words, in the inductive case, solve the problem for $I$ under the assumption that it can be solved for $I_1$, .., $I_k$.

Example. Let us reproduce the function above:

sum :: [Int] -> Int
-- base case (the input list has size 0)
sum [] = 0
-- inductive case (the input list has size n + 1)
sum (x : xs) = x + sum xs

In this example, the input $I$ is a list.

• In the base case ($I$ is the empty list), we solve the problem directly by returning 0.
• In the inductive case, $I$ is of the form $(a \colon I_1)$, where $a$ is an integer and $I_1$ is a list. In this case, the sub-list $I_1$ is our (unique) smaller input. We:
  • solve the problem for $I_1$ by calling the function sum recursively, and
  • use the result of sum $I_1$ to solve the problem for the full list $I$, assuming that the recursive call is correct.

Hint. When the input $I$ is a list, the tail of $I$ is often a good candidate for a recursive call.

Correctness #

Correctness of the whole algorithm holds by induction on the size of the input, observing that:

• the base case is correct, and
• in the inductive case, if the recursive calls are correct, then function/method is correct.

Example. In the example above:

$a)$ The base case is clearly correct:

sum [] = 0

$b)$ In the inductive case, if the recursive call sum xs is correct, then the function is also clearly correct:

sum (x : xs) = x + sum xs

From these two observations $a)$ and $b)$, we can conclude that the function is correct for an input $I$ of any size:

• $0)$ If $I$ has size $0$ (i.e. if it is empty), then from $a)$, the function is correct.

• $1)$ If $I$ has size $1$, then the recursive call sum xs takes as input a list of size $0$.
  From $0)$, this recursive call is correct.
  So from $b)$, the function is correct for $I$.

• $2)$ If $I$ has size $2$, then the recursive call sum xs takes as input a list of size $1$.
  From $1)$, this recursive call is correct.
  So from $b)$, the function is correct for $I$.

• …

• $n)$ …

• $n+1)$ If $I$ has size $n +1$, then the recursive call sum xs takes as input a list of size $n$.
  From $n)$, this recursive call is correct.
  So from $b)$, the function is correct for $I$.

Examples #

Reminder. Some of the exercises below ask you to reimplement functions that are already available in the Haskell Prelude. If you want to test your code, you need to give them different names (for instance length' instead of length).

length :: [a] -> Int

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

reverse :: [a] -> [a]

reverse :: [a] -> [a]
reverse [] = []
reverse (x : xs) = reverse xs ++ [x]

endsWith :: (Eq a) => a -> [a] -> Bool

endsWith :: (Eq a) => a -> [a] -> Bool
-- empty list
endsWith _ [] = False
-- list of size 1
endsWith x [y] = x == y
-- list of size  > 1
endsWith x (_ : xs) = endsWith x xs

map :: (a -> b) -> [a] -> [b]

filter :: (a -> Bool) -> [a] -> [a]

any :: (a -> Bool) -> [a] -> Bool

all :: (a -> Bool) -> [a] -> Bool

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x: xs) = f x : map f xs

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter f (x : xs)
  | f x = x : filter f xs
  | otherwise = filter f xs

any :: (a -> Bool) -> [a] -> Bool
any _ [] = False
any f (x : xs) = f x || any f xs

all :: (a -> Bool) -> [a] -> Bool
all _ [] = True
all f (x : xs) = f x && all f xs

zip :: [a] -> [b] -> [(a,b)]

zip ['a','b','c'] [1,2]

zip :: [a] -> [b] -> [(a,b)]
zip _ [] = []
zip [] _ = []
zip (x : xs) (y : ys) = (x,y) : zip xs ys

takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile f (x : xs) | f x = x : takeWhile f xs
                     | otherwise = []

myFunction :: String -> String
myFunction = reverse . takeWhile (/= ' ') . reverse