Apakah "secara induktif" dan "secara rekursif" memiliki makna yang sangat mirip?

Apakah "secara induktif" dan "secara rekursif" berarti sangat mirip?

Misalnya, jika ada algoritma yang menentukan vektor n-dim dengan menentukan komponen k +1 pertama berdasarkan komponen k pertama yang telah ditentukan, dan diinisialisasi dengan komponen pertama, akankah Anda menyebutnya bekerja secara rekursif atau induktif? Saya telah menggunakan "secara rekursif", tetapi hari ini seseorang mengatakan "secara induktif".

Tidak , tapi bukan karena alasan yang diberikan orang lain. Perbedaan antara rekursi dan induksi bukanlah rekursi "top-down" dan induksi "bottom-up." Induksi adalah isomorfik terhadap sesuatu yang disebut "rekursi primer," tetapi, secara umum, rekursi lebih kuat daripada induksi .

Perbedaan antara top-down dan bottom-up adalah sepele - program rekursif primitif "top-down" apa pun dapat dikonversi secara mekanis menjadi sesuatu yang "bottom-up". Bahkan, setiap bukti dengan induksi dapat diubah menjadi program rekursif. Dalam kerangka kalkulus konstruksi induktif, jika Anda ingin membuktikan bahwa setiap bilangan alami adalah populasi, Anda akan menuliskannya sebagai fungsi yang membangun bukti bahwa n merupakan populasi dengan membuat panggilan rekursif untuk membangun bukti yang tidak 1 adalah froopulous.

Faktor kunci dari induksi adalah bahwa hal-hal didefinisikan dalam hal yang lebih kecil, dan mereka "keluar" setelah banyak langkah. Bilangan natural bersifat induktif karena setiap natural adalah 0, atau penerus natural yang lebih kecil. Daftar bersifat induktif karena setiap daftar kosong, atau dapat dipecah ("dibuka") menjadi elemen dan daftar yang lebih kecil.

Kadang-kadang program rekursif tidak ditulis dalam hal yang lebih kecil. Misalnya, ambil fungsi Collatz ini:

fun collatz(n) 
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

Fungsi ini tidak berjalan dari atas ke bawah atau dari bawah ke atas, dan karenanya tidak induktif terhadap bilangan asli.

Mungkin ada pemesanan untuk memperlakukannya secara induktif, tetapi untuk sebagian besar hal tidak mungkin. Fungsi lebih dari aliran tak terbatas adalah contoh yang bagus. Faktanya, stream adalah contoh prototipe dari tipe "coinductive".

"Yayasan Praktis untuk Bahasa Pemrograman" karya Bob Harper, tersedia online gratis, memiliki pengantar yang bagus untuk tipe induktif, koinduktif, dan rekursif.

Bagi saya itu sebagian besar adalah masalah sudut pandang. Jika saya mendefinisikan objek berdasarkan yang lebih kecil, saya melakukannya secara induktif, sehingga itu dari bawah ke atas. Jika saya memecahkan masalah dengan memecahnya menjadi potongan-potongan kecil yang diselesaikan dengan cara yang sama saya menyebutnya rekursi, itu adalah top-down.

(edit) PS. Lihat pertanyaan serupa di departemen Matematika kami, definisi Rekursif vs induktif . Saya mengutip dari jawaban Carl Mummert:

Deskripsi terbaik saya adalah bahwa "definisi induktif" lebih umum ketika kita mendefinisikan satu set objek "dari ketiadaan", sedangkan "definisi rekursif" lebih umum ketika kita mendefinisikan suatu fungsi pada kumpulan objek yang sudah ada.

Tetapi yang lebih penting:

tidak layak untuk tidur lebih lama

Tidak, mereka tidak sama. Dan Anda benar (saya berasumsi tentang algoritma yang Anda gambarkan): itu rekursif.

Alasannya adalah definisi dari kedua kata, yang dapat Anda baca di kamus atau Wikipedia.

Induksi (dengan asumsi 'induksi matematika') secara khusus tentang membuktikan bahwa semua kasus argumen benar.

Rekursi secara khusus tentang suatu proses yang mungkin diulang dengan cara tertentu dalam proses yang sama.

RE: jawaban orang lain:

Setelah melihat jawaban orang lain, saya bisa mengerti mengapa ada kebingungan: ketika mendefinisikan struktur data, fungsi, dan bahasa beberapa ahli teori tampaknya menggunakan 'induktif' dan 'rekursif' dengan cara yang membingungkan (lihat komentar untuk pertanyaan ini). Saya tidak berpikir jawaban Koppel (bahkan dengan suara tertinggi saat ini) benar-benar mencerminkan kebingungan itu. Karena kita berbicara tentang suatu algoritma, saya tidak akan mengatakan ada 'algoritma induktif'; Saya pikir itu kategorisasi yang tidak perlu.