# Counting Element Occurrences in a Linked List with Python Recursion

Rate this post

π‘ Problem Formulation: In this article, we are tackling the challenge of counting the number of times a particular element appears within a linked list using Python’s recursive capabilities. For instance, given a linked list `3 -> 1 -> 5 -> 1 -> 2` and the target element `1`, the desired output is `2` as the element `1` occurs twice.

## Method 1: Basic Recursion

This method involves defining a recursive function that traverses the linked list, checking for the target element at each node, and counting its occurrences. The function recursively calls itself with the next node until it reaches the end of the linked list.

Here’s an example:

```class Node:
def __init__(self, data):
self.data = data
self.next = None

def count_occurrences(node, target):
if node is None:
return 0
return (node.data == target) + count_occurrences(node.next, target)

# Example Usage:
```

Output: `2`

This code snippet defines a linked list and a function `count_occurrences` which counts the number of times a given element `target` appears in the list. The use of recursion makes it elegant and straightforward to follow. We initiate the count with the head of the list, and the function takes care of the rest.

## Method 2: Tail Recursive Approach

The tail recursive approach modifies the basic recursive method to be tail-call optimized, potentially improving the performance by limiting the size of the call stack. The function is designed such that the recursive call is the last operation performed by the function.

Here’s an example:

```def count_occurrences_tail(node, target, count=0):
if node is None:
return count
return count_occurrences_tail(node.next, target, count + (node.data == target))

# Example usage:
```

Output: `2`

In this snippet, `count_occurrences_tail` implements tail recursion by maintaining a running `count` of occurrences, which is passed along with each function call. By including the count in the function parameters, it prevents the need for additional stack space used by non-tail recursive functions.

## Method 3: Closure for Encapsulation

This method uses a closure to encapsulate state, which can help to maintain an internal counter that is not exposed outside the recursive function, preserving the function’s purely recursive nature.

Here’s an example:

```def make_counter():
def count_occurrences(node, target):
if node is None:
return 0
return (node.data == target) + count_occurrences(node.next, target)
return count_occurrences

# Example usage:
count_occurrences = make_counter()
```

Output: `2`

The snippet defines a `make_counter` factory function that returns the recursive counting function. This wrapper preserves the encapsulation, thereby making the recursive function inside less dependent on its environment and more re-usable.

## Method 4: Recursion with Lambda Expression

This method uses a lambda function within the recursive function to minimize code and provide a more functional programming style approach.

Here’s an example:

```count_occurrences = (lambda f: lambda node, target: f(f, node, target))(lambda self, node, target: 0 if node is None else (node.data == target) + self(self, node.next, target))

# Example usage:
```

Output: `2`

This one-liner defines `count_occurrences` as a lambda function that self-applies to express recursion compactly. While concise, readability may be compromised, which can make understanding and debugging more challenging.

## Bonus One-Liner Method 5: Recursion with List Comprehension

Combining recursion with Python’s list comprehension feature allows for an elegant one-liner function definition that remains surprisingly readable.

Here’s an example:

```count_occurrences = lambda node, target: 0 if node is None else [node.data == target, count_occurrences(node.next, target)]

# Unpacking in example usage:
Output: `2`