Я понял основы рекурсии. Я понял такие функции, как последовательность Фибоначчи и факториал, и то, как значение возвращается в вызываемую функцию.
Я нашел этот код для Mergesort и модифицировал его, добавив несколько операторов печати, чтобы понять ход программы. Мне жаль, что это долго.
def mergeSort(alist):
print("Splitting ", alist)
if len(alist) > 1:
mid = len(alist)//2
lefthalf = alist[:mid]
print("lefthalf created as a result of splitting", lefthalf)
righthalf = alist[mid:]
print("righthalf created as a result of splitting", righthalf)
print("Calling mergesort on lefthalf")
mergeSort(lefthalf)
print("Calling mergesort on righthalf")
mergeSort(righthalf)
i=0
j=0
k=0
print("Merging begins")
print("lefthalf, righthalf is ", lefthalf, righthalf)
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
k=k+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
else:
print("Returning to the line after the calling function")
return
alist = [5, 6, 7, 8, 0]
mergeSort(alist)
print(alist)
Я понял, как работает логика слияния. Что я хочу понять, так это то, что после слияния левой половины и правой половины наименьших подмассивов, как он запоминает, где остановился?
Операторы печати, сгенерированные приведенным выше кодом:
Splitting [5, 6, 7, 8, 0]
lefthalf created as a result of splitting [5, 6]
righthalf created as a result of splitting [7, 8, 0]
Calling mergesort on lefthalf
Splitting [5, 6]
lefthalf created as a result of splitting [5]
righthalf created as a result of splitting [6]
Calling mergesort on lefthalf
Splitting [5]
Returning to the line after the calling function
Calling mergesort on righthalf
Splitting [6]
Returning to the line after the calling function
Merging begins
lefthalf, righthalf is [5] [6]
Calling mergesort on righthalf
Splitting [7, 8, 0]
lefthalf created as a result of splitting [7]
righthalf created as a result of splitting [8, 0]
Calling mergesort on lefthalf
Splitting [7]
Returning to the line after the calling function
Calling mergesort on righthalf
Splitting [8, 0]
lefthalf created as a result of splitting [8]
righthalf created as a result of splitting [0]
Calling mergesort on lefthalf
Splitting [8]
Returning to the line after the calling function
Calling mergesort on righthalf
Splitting [0]
Returning to the line after the calling function
Merging begins
lefthalf, righthalf is [8] [0]
Merging begins
lefthalf, righthalf is [7] [0, 8]
Merging begins
lefthalf, righthalf is [5, 6] [0, 7, 8]
[0, 5, 6, 7, 8]
Я хочу понять из приведенных выше операторов печати, как он вспомнил, чтобы вернуться к
Calling mergesort on righthalf
Splitting [7, 8, 0]
после того, как он объединил [5] и [6] в [5 6]
Это подошло к концу операторов в условии if len(alist) > 1:. Как он узнал, что «у меня не расщеплена и не слита правая половина»? Может ли кто-нибудь помочь мне здесь?
Для factorial(n) и fib(n) было довольно просто понять, что значение возвращается в вызывающую функцию, и понять, как выполняется return n + calledfunction(n) в рекурсивном случае. Но внутри условия if нет оператора return.
