4.12.3.1Functional ProgrammingCore

Functional Lists and Recursive Processing

A non-empty list can be viewed as its first element and the list of remaining elements. Handle the empty case explicitly before taking a head or recursing on a tail.

35 min Functions and Lists

What you'll be able to do

Use head, tail, length and empty-list operations
Construct lists by prepend and append
Explain immutable list processing and representation costs

Separate an element from a list

For [4,3,5], the head is the element 4 and the tail is the list [3,5]. The tail of a one-element list is empty, not an absent numerical value. The empty list has length zero and has no head under the ordinary model.

A recursive list algorithm can stop at empty and otherwise process the head followed by the tail. This structure follows the data definition. Check the empty case before accessing index zero in a Python demonstration, because an empty list does not provide that position.

Construct rather than mutate

Prepending x constructs a list with x before the existing elements; appending places it after them. A functional style can return a new list rather than changing the original in place. Python [x]+values and values+[x] illustrate these meanings without claiming to be constant-time linked-list operations.

An immutable linked-list model can share a tail efficiently, while Python slicing creates a new outer list. Therefore, repeated tail slicing can add copying costs. Distinguish the abstract operation from the representation used to demonstrate it, especially when analysing time or space.

Trace a recursive result

For a sum, empty gives zero and a non-empty list gives head plus the sum of its tail. For a length, empty gives zero and each non-empty level contributes one. The recursive problem size decreases because the tail has one fewer element.

Newly constructed outer lists can still contain shared mutable objects. A pure style needs attention to those elements and to hidden state, not just avoidance of one append call. Use small tests containing empty, one-element and several-element lists to check both structural rules and expected results.

Python 3

def total(values):
    if values == []:
        return 0
    return values[0] + total(values[1:])

original = [4, 3, 5]
prepended = [9] + original
appended = original + [9]
print(total(original), prepended, appended)
print(original)

Scroll horizontally to see the full code or table.

The slicing version is pedagogical and makes copies; original is not changed.

Work through the problem

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.

Example 1Give the head and tail of [7].

1The head is the first element, 7.

2No elements remain, so the tail is the empty list.

AnswerHead 7; tail [].

Example 2Trace total([4,3,5]).

1The recursive expansion is 4+(3+(5+0)).

2The empty-list base case supplies zero and unwinding gives 12.

Answer12.

Common mistakes to avoid

Returning a single element when the operation requires a tail list.

Distinguish element type from list type.

Ignoring copying costs in the demonstration language.

Attach complexity to the actual representation.

Key takeaways

Head and tail expose recursive structure.
Empty lists need explicit base cases.
Functional behaviour and storage implementation are separate.

Test yourself

Answer a few questions, then review anything you missed.

Next step

Keep practising

Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.

Browse practice topics

Related lessons

All 3 lessons

def total(values): if values == []: return 0 return values[0] + total(values[1:]) original = [4, 3, 5] prepended = [9] + original appended = original + [9] print(total(original), prepended, appended) print(original)