# Exploring Recursive Strategies to Find the Length of a Linked List in Python

Rate this post

π‘ Problem Formulation: In this article, we tackle the challenge of determining the length of a linked list using recursion in Python. Specifically, we aim to write a Python function that, given the head node of a singly linked list, returns the number of nodes it contains. For instance, inputting a linked list with nodes [1, 2, 3, 4] should yield an output of 4, as there are four nodes in the list.

## Method 1: Classic Recursive Approach

This classic recursive method involves a function that calls itself with the next node until it reaches the end of the linked list. The function definition is `def find_length_recursive(node):`, which returns the length of the linked list starting from the given node.

Here’s an example:

```class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

def find_length_recursive(node):
if not node:
return 0
return 1 + find_length_recursive(node.next)

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Output:

`4`

The function `find_length_recursive()` checks if the current node is `None`, the base case indicating the end of the list, and returns 0. Otherwise, it returns 1 plus the result of calling itself on the next node, effectively counting each node in the chain.

## Method 2: Tail Recursive Approach

Tail recursion optimizes the classic approach by passing the accumulated length along with the next node to avoid adding stack frames. We define a helper function within our main function, `def find_length_tail_recursive(node):`, to implement this strategy.

Here’s an example:

```def find_length_tail_recursive(node):
def recurse(node, count):
if not node:
return count
return recurse(node.next, count + 1)
return recurse(node, 0)

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Output:

`4`

The inner function `recurse()` is defined within `find_length_tail_recursive()` and adds a parameter `count` which holds the current length of the list as the recursion unwinds. When the base case is reached, the accumulated count is returned.

## Method 3: External Counter Approach

Instead of passing the count within the recursive calls, we can use an external counter that gets updated with each recursion. This method also defines a recursive function: `def find_length_external_counter(node, count):` which modifies the external counter to compute the length.

Here’s an example:

```count = 0

def find_length_external_counter(node):
global count
if not node:
return count
count += 1
return find_length_external_counter(node.next)

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Output:

`4`

The global variable `count` keeps track of the length of the linked list. With each recursive call of `find_length_external_counter()`, `count` is incremented until the end of the list is reached.

## Method 4: Class Attribute Approach

Another way to track the length is by using a class attribute to store the count. This approach uses a class with a recursive method, `find_length_class_attribute(self, node):`, to encapsulate the linked list and its length logic.

Here’s an example:

```class LinkedList:
def __init__(self):
self.count = 0

def find_length_class_attribute(self, node):
if not node:
return self.count
self.count += 1
return self.find_length_class_attribute(node.next)

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Output:

`4`

The `LinkedList` class has an attribute `count` which is updated by the method `find_length_class_attribute()` as it recursively processes each node. Upon reaching the end of the list, `count` reflects the total length.

## Bonus One-Liner Method 5: Recursive Lambda Function

The quintessence of brevity, this method uses a recursive lambda function to determine the length. The one-liner solution is defined as `find_length_lambda = lambda node: 0 if not node else 1 + find_length_lambda(node.next)`, making it a concise and elegant approach.

Here’s an example:

```find_length_lambda = lambda node: 0 if not node else 1 + find_length_lambda(node.next)

head = ListNode(1, ListNode(2, ListNode(3, ListNode(4))))

Output:

`4`

The lambda function `find_length_lambda` operates similarly to the classic recursive method but in a compact form. It uses a ternary conditional operator to return 0 for the base case, or 1 plus the recursive call on the next node otherwise.

## Summary/Discussion

• Method 1: Classic Recursive Approach. Strengths: Simple and clear. Weaknesses: Basic recursion can lead to stack overflow for long lists.
• Method 2: Tail Recursive Approach. Strengths: Optimized stack usage. Weaknesses: Python does not inherently optimize tail recursion like some other languages.
• Method 3: External Counter Approach. Strengths: Removes the need for additional parameters. Weaknesses: Relies on global state, which can lead to bugs.
• Method 4: Class Attribute Approach. Strengths: Encapsulates state within a class. Weaknesses: Requires an additional class structure.
• Method 5: Recursive Lambda Function. Strengths: Extremely concise. Weaknesses: May be less readable for those unfamiliar with lambda functions or recursion.