递归获取链表的第 N 个值

Question

我希望能够递归传递count或递增计数，然后将其传递到我的递归中。但是，我知道我必须声明count = 0才能在递增时使用它。我仍在学习 python，我发现很难递归递增计数。有人可以帮我解决这个问题吗？

我知道目前我的代码是错误的，因为我所做的每次递归，计数都会被重新发送到 0。我不想将计数设置为第三个参数，因为我觉得没有必要。

我的代码：

def getNth(head, n):
    count = 0
    if count == n:
        count += 1
        return head.value
    else:
        if head.next is not None:
            getNth(head.next,n)
        else:
            print 'not in linked list'

Answer 1

倒

数而不是向上计数。

def getNth(head, n):
    if n == 0:
        return head.value
    return getNth(head.next, n - 1)

然而，这在实践中会表现得很糟糕，如果你的列表长度合理，你会得到一个堆栈溢出。函数式编程风格通常不是好的Python风格(因为，例如，尾递归不是Python的一个功能(。

我只是把循环写出来。

def getNth(head, n):
   for _ in xrange(n):
       head = head.next
   return head.value

Answer 2

这是递

归中的常见模式，在python中净地执行，所以值得一提。

方法允许关键字参数，这对于跟踪递归深度很有用。 对方法签名的更改是微不足道的：

def getNth(head, n, count=0):

0 是 count 的默认参数。 只需在初始调用中省略它(或用count=0明确调用它(，您就可以了。 然后，您可以使用 getNth(*args, count + 1) 轻松递归调用getNth。

我现在应该注意，我已经解释过这一点，递归在 python 中非常慢。 如果你关心性能，你应该更喜欢迭代解决方案(通常涉及生成器(而不是递归解决方案。