使用递归查找链表长度的Python程序

什么是链表

链表是一种常见的数据结构，它由多个节点组成，每个节点存储着数据和下一个节点的地址。链表可以用来实现栈、队列等数据结构，其主要优点是可以方便地插入、删除节点，而不必移动其他元素。

如何遍历链表

要想遍历链表，可以使用循环或递归的方式。循环是比较常见的做法，我们可以从头节点开始，不断地跟着next指针向下遍历，直到遍历到空节点为止。下面是一个简单的Python程序，用来打印链表中的元素：

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

def print_list(head):
    while head:
        print(head.value)
        head = head.next

# 测试程序
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

n1.next = n2
n2.next = n3
n3.next = n4

print_list(n1)  # 输出1、2、3、4

递归查找链表长度

递归是一种常见的算法模式，它常用于树形结构的遍历，也可以用于链表。使用递归遍历链表时，我们可以将问题划分为一个个小的子问题，然后通过递归不断地解决这些子问题，最终得到总体的解决方案。

下面是一个递归程序，用来查找链表的长度：

def list_length(head):
    if not head:
        return 0
    return 1 + list_length(head.next)

# 测试程序
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)

n1.next = n2
n2.next = n3
n3.next = n4

print(list_length(n1))  # 输出4

在这个程序中，我们首先判断链表是否为空，如果是，则长度为0。否则，递归调用list_length函数，参数为head.next，即链表中下一个节点的指针。每次递归时，我们把当前节点的长度加1，最终返回所有节点的长度和。