def msort(li):
if len(li)>1:
if (len(li)%2)==0:
p=int(len(li)/2)
else:
p=int(((len(li))-1)/2)
print(li)
print(li[:p])
print(li[p:])
print('wwww')
msort(li[:p])
msort(li[p:])
return li
#main
li= [4,2,6,3]
print (li)
print ('aaaa')
li=msort(li)
print('xxxx')
print (li)
Chciałbym się zapytać dlaczego funkcja nie zwraca tylko pierwszego elementu listy (tutaj 4) lecz zwraca ją całą? Nie jest tak że, po dotarciu do return funkcja zwraca to co pod nim było?
To jest tylko fragment mergesorta. Poza tym czy nie powinna być tu zwracana lista jednoelementowa?
Może to wina przyzwyczajeń z C.
W Pythonie gdy utworzysz sobie listę:
C 
Python li = [1, 2, 3, 4]
to li będzie referencją do obiektu, który jest listą, z którego możesz wyciągać elementy, wywoływać jego metody (np. li.append(5)) czy wywoływać na nim funkcje (len(li)) :) li nie jest wskaźnikiem na pierwszy element tablicy ;)
if (len(li)%2)==0:
p=int(len(li)/2)
else:
p=int(((len(li))-1)/2)
To możesz uprościć, stosując trochę inny operator dzielenia (floor division):
```python
p = len(li) // 2 # z automatu zaokrągli w dół do liczby całkowitej
Czyli w Pythonie rekurencja nie zatrzymuje się na return?
W jaki sposób on później scala jednoelementowe listy?
Rekruencja w Pythonie działa normalnie, tak jak i w innych językach.
Jak scalane są listy jednoelementowe? Można zrobić to na dwa sposoby - albo utworzyć nową listę i rozpakować do niej dwie poprzednie, czyli np.
old_1 = [1]
old_2 = [2]
new_llist = []
new_list.extend(old_1)
new_list.extend(old_2)
Lub
old_1 = [1]
old_2 = [2]
new_llist = []
new_list.append(old_1[0])
new_list.append(old_2[0])
lub też
old_1 = [1]
old_2 = [2]
new_list = [*old_1, *old_2]
Druga rzecz, jaką warto wspomnieć, to przekazywanie argumentów.
Domyślnie mamy dwie metody przekazywania argumentów w funkcji w Pythonie - by reference i by value.
Rzeczy, które są immutable, w Pythonie lecą by value, czyli dostajesz tą skopiowaną wartość - standardowe zachowanie np. z C itd.. W innym wypadku przekazywana jest referencja. Czyli w przypadku list, masz takie jakby wskaźniki z C, czyli jeśli przekażesz listę jako argument do funkcji, zmodyfikujesz ją, to po wyjściu z funkcji, oryginalna lista będzie zmodyfikowana.
Mergesort, Możesz sobie porównać:
def merge_sort(alist):
if len(alist) > 1:
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]
merge_sort(lefthalf)
merge_sort(righthalf)
i = 0
j = 0
k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i += 1
else:
alist[k] = righthalf[j]
j += 1
k += 1
while i < len(lefthalf):
alist[k] = lefthalf[i]
i += 1
k += 1
while j < len(righthalf):
alist[k] = righthalf[j]
j += 1
k += 1
alist1 = [54, 26, 93, 17, 77, 31, 44, 55, 20]
merge_sort(alist1)
print(alist1)
'''
output -> [17, 20, 26, 31, 44, 54, 55, 77, 93]
'''
konto usunięte napisał(a):
Czyli w Pythonie rekurencja nie zatrzymuje się na return?
W Pythonie, jak w chyba każdym innym języku, jeżeli wywołasz funkcję, która wywoła samą siebie, musisz najpierw wrócić z wewnętrznego wywołania, by móc wrócić z zewnętrznego.
def FOO():
# cośtam cośtam, nieistotne
if warunek:
FOO()
return wynik
Wykona się mniej więcej w ten sposób:
WYWOŁANIE FOO (1-sze)
* WYKONANIE FOO (1-szego)
* WYWOŁANIE FOO (2-gie, rekurencyjne)
* * WYKONANIE FOO (2-giego)
[...]
* * * WYWOŁANIE FOO (N-te, rekurencyjnie)
* * * * WYKONANIE FOO (N-tego)
* * * * POWRÓT Z FOO (N-tego)
* * * POWRÓT Z FOO (N-1 - szego)
[...]
* * POWRÓT Z FOO (2-giego)
* POWRÓT Z FOO (1-szego)
W jaki sposób on później scala jednoelementowe listy?
Kto? mergesort? Mniej więcej w ten sposób:
lewa = mergesort(lista[:p])
prawa = mergesort(lista[p:])
posortowana = []
while len(lewa) > 0 and len(prawa) > 0:
if lewa[0] > prawa [0]:
posortowana.append(lewa.pop(0))
else:
posortowana.append(prawa.pop(0))
# Jeśli któraś nie jest pusta, dorzuci ją na koniec
posortowana = posortowana + lewa + prawa
return posortowana
Rekurencja w Pythonie niczym się nie różni od innych języków:
def rec_fun(arg):
if cond: return <something>
else: return F(rec_fun(g(arg)))
Przykład, suma liczb do n:
def a_sum(n):
if n == 0:
return 0;
else:
return n + a_sum(n - 1)
