Czy ten program zakończy się z każdą liczbą całkowitą?

W częściowym teście na przygotowanie GATE pojawiło się pytanie:

f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

Odpowiedziałem: „Zakończy się dla wszystkich liczb całkowitych”, ponieważ nawet w przypadku niektórych liczb całkowitych ujemnych zakończy się jako Błąd przepełnienia stosu .

Ale mój przyjaciel nie zgodził się z twierdzeniem, że skoro nie jest to zaimplementowany kod, a tylko pseudokod, w przypadku niektórych ujemnych liczb całkowitych będzie to nieskończona rekurencja.

Która odpowiedź jest prawidłowa i dlaczego?

algorithms recursion pseudocode

— prakhar londhe
źródło

Nie kończy się dla n = -1. W takich przypadkach bierze się pod uwagę głównie teoretyczne limity.

— Deep Joshi

Jeśli przepełnienie stosu ma być uważane za zakończenie, wszystkie programy zostaną zakończone, co

— przeczy

@ xuq01 while (true);nie zakończy się, ani, w uzasadniony sposób, nie spowoduje przepełnienia stosu.

— TripeHound

@leftaroundabout Prawdopodobnie nie powinienem był używać słowa „ na czymkolwiek rozsądnym ”, ponieważ jest to zupełnie inny poziom „ rozsądnego ” ... zauważanie i wdrażanie rekurencji ogona jest przyjemne (lub nawet rozsądne ), ale nie robienie tego jest tylko nieznacznie „ nie sensowne” „. Wszystko, co zostanie zaimplementowane while(true);w sposób wykorzystujący dowolny stos, zdecydowanie nie byłoby rozsądne . Chodzi o to, że dopóki celowo nie postawisz się niezręcznie, while(true);nie zakończy się ani nie spowoduje przepełnienia stosu.

— TripeHound

@ xuq01 Nie sądzę, że „zniszczenie wszechświata” liczy się jako rozwiązanie problemu zatrzymania.

— TripeHound,

Odpowiedzi:

Prawidłowa odpowiedź jest taka, że ta funkcja nie kończy się na wszystkich liczbach całkowitych (w szczególności nie kończy się na -1). Twój przyjaciel ma rację twierdząc, że jest to pseudokod, a pseudokod nie kończy się na przepełnieniu stosu. Pseudokod nie jest formalnie zdefiniowany, ale chodzi o to, że robi to, co jest napisane na puszce. Jeśli kod nie mówi „zakończ z błędem przepełnienia stosu”, oznacza to, że nie ma błędu przepełnienia stosu.

Nawet jeśli byłby to prawdziwy język programowania, poprawną odpowiedzią byłoby nadal „nie kończy się”, chyba że użycie stosu jest częścią definicji języka. Większość języków nie określa zachowania programów, które mogą przepełnić stos, ponieważ trudno jest dokładnie określić, ile stosu zużyje program.

Jeśli uruchomienie kodu na rzeczywistym interpretatorze lub kompilatorze powoduje przepełnienie stosu, w wielu językach, jest to rozbieżność między formalną semantyką języka a implementacją. Zrozumiałe jest, że implementacje języka będą działały tylko na konkretnym komputerze ze skończoną pamięcią. Jeśli program umiera z powodu przepełnienia stosu, należy kupić większy komputer, w razie potrzeby ponownie skompilować system w celu obsługi całej pamięci i spróbować ponownie. Jeśli program się nie kończy, być może będziesz musiał to robić wiecznie.

Nawet fakt, że program przepełni lub nie przepełni stosu, nie jest dobrze zdefiniowany, ponieważ niektóre optymalizacje, takie jak optymalizacja wywołania ogona i zapamiętywanie, mogą pozwolić na nieskończony łańcuch wywołań funkcji w stałej przestrzeni stosu. Niektóre specyfikacje językowe wymagają nawet, aby implementacje przeprowadzały optymalizację wywołania ogonowego, gdy to możliwe (jest to powszechne w funkcjonalnych językach programowania). Dla tej funkcji f(-1)rozwija się do f(f(-2)); zewnętrzne wywołanie do fjest wywołaniem ogonowym, więc nie wypycha niczego na stos, dlatego f(-2)trafia tylko na stos, a to zwraca -1, więc stos powraca do tego samego stanu, w jakim był na początku. Tak więc z optymalizacją ogona f(-1)pętle na zawsze w stałej pamięci.

— Gilles „SO- przestań być zły”
źródło

Przykładem, w którym kod przetłumaczony na język programowania nie powoduje przepełnienia stosu, jest Haskell. Po prostu zapętla się w nieskończoność:let f :: Int -> Int; f n = if even n then n `div` 2 else f (f (n - 1)) in f (-1)

— JoL

Jeśli spojrzymy na to pod kątem języka C, implementacja może dowolnie zamieniać kod na kod, który daje taki sam wynik we wszystkich przypadkach, w których oryginał nie wywołuje niezdefiniowanego zachowania. Więc może zastąpić

f(n):
   if n is even: f(n) = n/2
   else f(n) = f(f(n-1))

f(n):
   if n is even: f(n) = n/2
   else f(n) = f((n-1) / 2)

Teraz implementacja może zastosować rekurencję ogona:

f(n):
   while n is not even do n = (n-1) / 2
   f(n) = n/2

I to zapętla się na zawsze wtedy i tylko wtedy, gdy n = -1.

— gnasher729
źródło

Myślę, że w C, że wywoływanie f(-1)jest niezdefiniowanym zachowaniem (implementacja może zakładać, że każdy wątek kończy działanie lub robi coś innego na krótkiej liście działań, których ta funkcja nie wykonuje), więc kompilator może w rzeczywistości zrobić wszystko, co chce walizka!