Recursion Over Lists | CodeSignal Learn

Recursion Over Lists | CodeSignal Learn

Introduction To Recursion

Welcome to **Unit 6**! In the previous lesson, we explored how to generate and transform lists using **list comprehensions** . Now, we will look at how to process those lists step by step. In many programming languages, you process lists using for or while loops. However, **Haskell** does not have loop structures. Instead, it relies on a concept called recursion . Recursion simply means that a function calls itself to repeat work. You can think of recursion as eating a box of chocolates. You take one piece out (handling the current item), and you are left with a slightly smaller box of chocolates. You repeat this exact process on the smaller box until the box is completely empty. In this lesson, we will learn how to write our own **recursive functions** to process lists piece by piece.

Brief Recall: List Pattern Matching

Before we write our first recursive function, let us quickly recall how we pull lists apart. We first saw this in Unit 3 when we learned how to match patterns safely. When working with lists, we usually care about two specific patterns: [] : The empty list. This means there is nothing left to process. (x:xs) : A non-empty list. The x represents the head (the first item), and the xs represents the tail (the rest of the list). In recursion, these two patterns act as our blueprint. The empty list [] becomes our stopping point, which we call the base case . The non-empty list (x:xs) is where we do our work and call the function again, which we call the recursive case .

Summing A List

Let us build our first recursive function step by step. Our goal is to create a function named **sumList** that adds up all the numbers in a list of **Int** integers. First, we need to define our type signature and our base case. The base case tells the function when to stop. If we try to sum an empty list, the result should be 0 . Haskell sumList :: [Int] -> Int sumList [] = 0 By telling Haskell what to do with an empty list, we prevent the function from trying to repeat indefinitely. Next, we add our recursive case to handle lists that actually contain numbers. Haskell sumList :: [Int] -> Int sumList [] = 0 sumList (x:xs) = x + sumList xs In the second equation, we use the (x:xs) pattern. We take the first number x and add it to the result of calling sumList on the rest of the list xs . This shrinks the list by one element every time it runs. To see how this works in action, let us write out a small visual trace of what happens when we call sumList [1, 2, 3] : sumList [1, 2, 3] becomes 1 + sumList [2, 3] sumList [2, 3] becomes 2 + sumList [3] sumList [3] becomes 3 + sumList [] sumList [] hits our base case and becomes 0 The final math is 1 + 2 + 3 + 0, which equals 6 . Here is the complete code running inside a main function: Haskell sumList :: [Int] -> Int sumList [] = 0 sumList (x:xs) = x + sumList xs main :: IO () main = do print (sumList [1, 2, 3, 4]) Output: text 10

Sign up

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Counting Elements

Now, let us write a function to count how many items are in a list, rather than adding up their values. We will call this function **lengthList** . Just as before, we start with our base case. If the list is empty, its length is 0 . Haskell lengthList :: [Int] -> Int lengthList [] = 0 For the recursive case, we want to count the current item as 1 and then add the length of the rest of the list. Because we only care about counting the items and do not care about the actual values inside the list, we can use the wildcard_to ignore the head. Haskell lengthList :: [Int] -> Int lengthList [] = 0 lengthList (_:xs) = 1 + lengthList xs Using (_:xs) perfectly expresses our intent: "I see an item here, but I don't need its value. Just add 1 and keep counting the rest." This shows how recursion can care purely about the structure of a list. Let us see this in action: Haskell lengthList :: [Int] -> Int lengthList [] = 0 lengthList (_:xs) = 1 + lengthList xs main :: IO () main = do print (lengthList [10, 20, 30]) Output: text 3

Searching A List

For our final example, let us build a function called **member** that checks whether a specific number exists inside a list. It will return a **Bool** (**True** or **False**). This function takes two arguments: the target number and the list. Let us start with the base case. If we reach an empty list, it means we have searched everywhere and did not find the target. Therefore, the result is False . Haskell member :: Int -> [Int] -> Bool member _ [] = False Notice we use a wildcard_for the target number in the base case, because if the list is empty, the target does not matter — it is definitely not there! Now, let us add the recursive case. We need to check whether our target t matches the current head x . Haskell member :: Int -> [Int] -> Bool member _ [] = False member t (x:xs) = t == x || member t xs Here we use the || (OR) operator. The code t == x || member t xs means: "Return True if the target t equals the head x . Or, if it does not match, return the result of searching the rest of the list xs ." If t == x is True, Haskell stops looking and returns True immediately. If it is False, the recursion continues down the list. Let us test it with a number that exists in the list and one that does not: Haskell member :: Int -> [Int] -> Bool member _ [] = False member t (x:xs) = t == x || member t xs main :: IO () main = do print (member 3 [1, 2, 3]) print (member 9 [1, 2, 3]) Output: text True False