我认为这已经是尾递归了。但如果不是，我该怎么做呢？

Question

这不是问题的最佳标题，我同意。但我想不出别的东西。对不起。

在 Groovy 中编写一个简单的单链表代码，我想添加一个方法，该方法接受两个列表并将右侧的列表附加到左侧的列表。这是我想出的。

private static class Node {
    Node next = null
    def head

    @TailRecursive
    Node append(Node left = this, Node right) {
        if (!right) return left
        if (!left) return right

        if (!left.next) left.next = right
        else left.next = append(left.next, right)

        return left
    }
}

但是我得到了错误，

LinkedList.groovy: 23: Recursive call could not be transformed by @TailRecursive. Maybe it's not a tail call.
 @ line 23, column 30.
               else head.next = append(head.next, tail)

是不是因为最后的return语句不是尾递归？我该如何解决这个问题？

Answer 1

像下面这样的东西就足够了吗？

import groovy.transform.TailRecursive

@TailRecursive
LinkedList mergeLinkedList(LinkedList left = [], LinkedList right = []) {
    if ( !left ) {
        right
    } else if ( !right ) {
        left
    } else {
        left.add( right.head() )
        mergeLinkedList( left, right.tail() ) 
    }
}

def left = (1..100) as LinkedList, right = (200..500) as LinkedList

assert mergeLinkedList( left, right ) == ((1..100) + (200..500)) as LinkedList

Answer 2

根据user2864740给出的提示，这里是尾递归实现。它应该和我在问题中发布的非尾递归一样有效。

@TailRecursive
Node append(Node prevTail = this, Node tail = this?.next, Node right) {
    if (!right) return left
    if (!prevTail) return right

    if (!tail) prevTail.next = right
    else return append(tail, tail?.next, right)
}

我认为这已经是尾递归了。但如果不是，我该怎么做呢？

I thought this is already tail recursive. But if not how do I make it so?

recursion

groovy

tail-recursion