**π‘ 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) # Example LinkedList: 1->2->3->4 head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) print(find_length_recursive(head))

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) # Example LinkedList: 1->2->3->4 head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) print(find_length_tail_recursive(head))

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) # Example LinkedList: 1->2->3->4 head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) print(find_length_external_counter(head))

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) # Example LinkedList: 1->2->3->4 llist = LinkedList() head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) print(llist.find_length_class_attribute(head))

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) # Example LinkedList: 1->2->3->4 head = ListNode(1, ListNode(2, ListNode(3, ListNode(4)))) print(find_length_lambda(head))

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.