Apakah program ini akan berakhir untuk setiap Integer?

14

Dalam Tes Bagian untuk Persiapan GATE ada pertanyaan:

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

Saya menjawab "Ini akan berakhir untuk semua bilangan bulat", karena bahkan untuk beberapa bilangan bulat negatif, itu akan berakhir sebagai Stack Overflow Error .

Tetapi teman saya tidak setuju mengatakan bahwa karena ini bukan kode yang diimplementasikan dan hanya pseudocode, itu akan menjadi rekursi yang tak terbatas dalam kasus beberapa bilangan bulat negatif.

Jawaban mana yang benar dan mengapa?

algorithms recursion pseudocode prakhar londhe
sumber
8
Itu tidak diakhiri untuk n = -1. Sebagian besar batasan teoretis dipertimbangkan dalam kasus seperti itu.
Deep Joshi
9
Jika stack overflow dianggap sebagai pemutusan, maka semua program akan berakhir dan mengalahkan tujuan dari pertanyaan ini ...
xuq01
10
@ xuq01 while (true);tidak akan berhenti atau, pada apa pun yang masuk akal, menyebabkan stack overflow.
TripeHound
3
@leftaroundabout Saya mungkin tidak seharusnya menggunakan " pada apa pun yang masuk akal " karena ini tingkat yang sama sekali berbeda dari " masuk akal " ... melihat dan menerapkan rekursi ekor itu bagus (atau bahkan masuk akal ), tetapi tidak melakukannya hanya sedikit " tidak masuk akal ". Apa pun yang diimplementasikan while(true);dengan cara yang menggunakan tumpukan apa pun pasti tidak masuk akal . Intinya adalah, kecuali Anda dengan sengaja keluar dari jalan Anda untuk menjadi canggung, while(true);tidak akan mengakhiri atau memicu stack overflow.
TripeHound
14
@ xuq01 Saya tidak berpikir "penghancuran alam semesta" dianggap sebagai solusi untuk masalah penghentian.
TripeHound

Jawaban:

49

Jawaban yang benar adalah bahwa fungsi ini tidak berakhir untuk semua bilangan bulat (khususnya, ini tidak berakhir pada -1). Teman Anda benar dalam menyatakan bahwa ini adalah pseudocode dan pseudocode tidak berakhir pada stack overflow. Pseudocode tidak didefinisikan secara formal, tetapi idenya adalah bahwa ia melakukan apa yang dikatakan pada kaleng. Jika kode tidak mengatakan "berakhir dengan kesalahan stack overflow" maka tidak ada kesalahan stack overflow.

Bahkan jika ini adalah bahasa pemrograman nyata, jawaban yang benar masih akan "tidak berakhir", kecuali penggunaan tumpukan adalah bagian dari definisi bahasa. Sebagian besar bahasa tidak menentukan perilaku program yang mungkin menumpuk stack, karena sulit untuk mengetahui dengan tepat berapa banyak tumpukan program yang akan digunakan.

Jika menjalankan kode pada juru bahasa atau kompiler yang sebenarnya menyebabkan stack overflow, dalam banyak bahasa, itu adalah perbedaan antara semantik formal bahasa dan implementasi. Secara umum dipahami bahwa implementasi suatu bahasa hanya akan melakukan apa yang dapat dilakukan pada komputer beton dengan memori yang terbatas. Jika program mati dengan stack overflow, Anda seharusnya membeli komputer yang lebih besar, mengkompilasi ulang sistem jika perlu untuk mendukung semua memori itu, dan coba lagi. Jika program ini tidak berakhir maka Anda mungkin harus terus melakukan ini selamanya.

Bahkan fakta bahwa suatu program akan atau tidak akan meluap stack tidak terdefinisi dengan baik, karena beberapa optimasi seperti optimasi panggilan ekor dan memoisasi dapat memungkinkan rantai panggilan fungsi tak terbatas dalam ruang stack terikat-konstan. Beberapa spesifikasi bahasa bahkan mengamanatkan bahwa implementasi melakukan optimasi panggilan ekor bila memungkinkan (ini umum dalam bahasa pemrograman fungsional). Untuk fungsi ini, f(-1)perluas untuk f(f(-2)); panggilan luar ke fadalah panggilan ekor sehingga tidak mendorong apa pun di tumpukan, sehingga hanya f(-2)masuk ke tumpukan, dan itu kembali -1, sehingga tumpukan kembali ke keadaan yang sama seperti di awal. Jadi dengan f(-1)pengulangan ekor panggilan optimasi selamanya dalam memori konstan.

Gilles 'SO- berhenti menjadi jahat'
sumber
3
Contoh di mana kode yang diterjemahkan ke bahasa pemrograman menghasilkan tidak ada stack overflow adalah Haskell. Itu hanya loop tanpa batas:let f :: Int -> Int; f n = if even n then n `div` 2 else f (f (n - 1)) in f (-1)
JoL
5

Jika kita melihat ini dalam bahasa C, sebuah implementasi bebas untuk mengganti kode dengan kode yang menghasilkan hasil yang sama dalam semua kasus di mana aslinya tidak memunculkan perilaku yang tidak terdefinisi. Jadi bisa diganti

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

dengan

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

Sekarang implementasinya diizinkan untuk menerapkan rekursi ekor: 

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

Dan ini loop selamanya jika dan hanya jika n = -1.

gnasher729
sumber
Saya pikir, dalam C, bahwa memohon f(-1)adalah perilaku yang tidak terdefinisi (implementasinya dapat mengasumsikan bahwa setiap utas berakhir atau melakukan sesuatu yang lain dalam daftar pendek kegiatan yang tidak dilakukan fungsi ini), sehingga kompiler dapat benar-benar melakukan apa pun yang diinginkannya dalam kasus!