Блог

Главная - Вопросы по программированию - Использование рекурсии для объединения двух связанных списков — когда мы переходим к следующей строке рекурсивного вызова?

Использование рекурсии для объединения двух связанных списков — когда мы переходим к следующей строке рекурсивного вызова?

#python #recursion

Вопрос:

У меня есть рекурсивное решение вопроса: https://leetcode.com/problems/merge-two-sorted-lists/

 class Solution:
    def mergeTwoLists(self, l1, l2):
        if l1 is None:
            return l2
        elif l2 is None:
            return l1
        elif l1.val < l2.val:
            l1.next = self.mergeTwoLists(l1.next, l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1, l2.next)
            return l2

Есть только одна вещь, которую я не совсем понимаю, и это return l1 «и return l2 сразу после recursive calls «.

Я вижу, что происходит в целом, в том, что мы уменьшаем проблему с каждым рекурсивным вызовом, перемещая один (l1,l2.next) из них вдоль или (l1,l2.next) до тех пор, пока мы не достигнем базового варианта.

Чтобы задать более прямой вопрос, когда return l1 and return l2 выполняется — строки сразу после рекурсивных вызовов? Выполняются ли они после каждого рекурсивного вызова или только после того, как мы достигнем базового варианта? Потому что, насколько я понимаю из других вопросов, мы переходим к следующей строке рекурсивного вызова только тогда, когда мы исчерпали сам рекурсивный вызов (т. Е. Достигли базового варианта)- это правильно?

Еще один вопрос — когда мы return l1 или return l2 после рекурсивных вызовов, правильно ли я понимаю, что мы, по сути, «печатаем» l1 или l2, чтобы они стали частью окончательного ответа?

Метки: