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?

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.

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))

z

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.