Я думал, что это уже хвост рекурсивный. Но если нет, то как мне сделать это так?

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

Основываясь на подсказке, user2864740 дал пользователь 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)
}

Answer 2

Что-то вроде ниже будет достаточно?

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