Sejarah rekursi

14

Siapa yang memperkenalkan gagasan rekursi ?
Dapatkah seseorang menjelaskan dari mana asalnya dan bagaimana pengaruhnya terhadap ilmu komputer?

reference-request ho.history-overview recursion Srinivas Reddy Thatiparthy
sumber

5

Pertanyaan ini mungkin terlalu luas: "dampak rekursi pada ilmu komputer"? Juga, judul yang lebih spesifik untuk pertanyaan itu akan menyenangkan.

Shane

19

Komputasi dan Rekursi, oleh Soare. http://www.people.cs.uchicago.edu/~soare/History/compute.pdf

Makalah ini adalah yang pertama dari sejarah makalah perhitungan yang tersedia di sini: http://www.people.cs.uchicago.edu/~soare/History/

Aaron Sterling
sumber

1

Bagian 2.2 berjudul "The Origin of Recursion."

Aaron Sterling

5

Sangat menarik untuk melihat akun matematika ini tentang sejarah rekursi. Saya bingung pertanyaan ini untuk sejarah konsep resusi, yang tidak diragukan lagi telah menjadi andalan pemikiran manusia untuk setidaknya sejauh kita memiliki literatur yang baik.

Ross Snider

Lihat juga artikel Soare di "Handbook of Computability Theory", 1999.

Kaveh

Bisakah seseorang tolong jelaskan leluconnya pada penutur asing yang kebingungan ini? Menurut Google, "resusi" adalah (1) salah mengeja "rekursi", atau (2) nama merek tas Arthur & Aston. Atau apakah itu seharusnya terhubung ke "cusion" entah bagaimana? Atau untuk "makian"?

Emil Jeřábek mendukung Monica

1

@Emil, ini adalah Telur Paskah Google yang mencari rekursi merujuk ke halaman pencarian itu sendiri.

Kaveh

6

Bukan yang pertama, tetapi penting sejauh aplikasi praktis yang bersangkutan: "Fungsi Rekursif Ekspresi Simbolik dan Komputasi Mereka dengan Mesin, Bagian I" oleh John McCarthy (di mana ia memperkenalkan Lisp)

Shane
sumber

2

Mungkin sedikit singgung pertanyaan awal, tetapi entri blog " Bagaimana rekursi masuk ke pemrograman: komedi kesalahan " menggambarkan bagian yang menarik dari sejarah komputasi awal.

Martin Berger
sumber

2

Dari artikel Fungsi Rekursif pada SEP :

Penggunaan rekursi kembali ke abad ke-19. Dedekind [1888] menggunakan gagasan untuk memperoleh fungsi yang diperlukan dalam analisis formalnya tentang konsep bilangan alami. Dalam logika, rekursi muncul dalam Skolem [1923], di mana dicatat bahwa banyak fungsi dasar dapat didefinisikan oleh aplikasi sederhana dari metode ini. Formalisasi dan pengembangan gagasan modern ini disebabkan oleh sejumlah orang, terutama Gödel [1931], Herbrand, Rózsa Péter [1951] dan Kleene [1936]. Kleene pada tahun 1952 menggambarkan Péter sebagai "kontributor terkemuka untuk teori khusus fungsi rekursif". Dia mempresentasikan makalah tentang fungsi rekursif di Kongres Matematikawan Internasional di Zurich pada tahun 1932.

Ini menyarankan yang berikut untuk informasi lebih lanjut:

Rod Adams, " Sejarah Awal Fungsi Rekursif dan Komputasi dari Gödel hingga Turing ", 2011.

Khususnya lihat bagian berjudul " Definisi Rekursif Pertama " di halaman 5.

Kaveh
sumber

1

Saya tidak tahu kapan itu muncul, tetapi solusi rekursif untuk Towers of Hanoi sering digunakan sebagai contoh pengantar. Masalahnya berasal sebelum pendekatan formal pada perhitungan.

Raphael
sumber

2

Tidak juga. Menara Hanoi ditemukan oleh Edouard Lucas pada tahun 1883, yang agak lama setelah pendekatan formal pertama untuk perhitungan oleh Babbage dan Ada Lovelace (makalahnya diterbitkan pada tahun 1843).

Jeffrey Shallit

Sejarah rekursi

Jawaban: