Bagaimana cara menentukan runtime dari fungsi rekursif ganda?

Dengan adanya fungsi rekursif ganda sewenang-wenang, bagaimana cara menghitung waktu menjalankannya?

Sebagai Contoh (dalam pseudocode):

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

Atau sesuatu seperti itu.

Metode apa yang bisa atau harus digunakan seseorang untuk menentukan sesuatu seperti ini?

Anda terus mengubah fungsi Anda. Tetapi tetap memilih yang akan berjalan selamanya tanpa konversi ..

Rekursi menjadi rumit, cepat. Langkah pertama untuk menganalisis fungsi rekursif ganda yang diusulkan adalah mencoba melacaknya pada beberapa nilai sampel, untuk melihat apa fungsinya. Jika perhitungan Anda masuk ke loop tak terbatas, fungsi tersebut tidak didefinisikan dengan baik. Jika perhitungan Anda menjadi spiral yang terus mendapatkan angka yang lebih besar (yang terjadi dengan sangat mudah), itu mungkin tidak didefinisikan dengan baik.

Jika menelusurinya memberikan jawaban, Anda kemudian mencoba memunculkan beberapa pola atau hubungan berulang antara jawaban. Setelah Anda memilikinya, Anda dapat mencoba mencari tahu runtime-nya. Mencari tahu itu bisa sangat, sangat rumit, tetapi kami memiliki hasil seperti teorema Master yang memungkinkan kami menemukan jawabannya dalam banyak kasus.

Berhati-hatilah bahwa bahkan dengan rekursi tunggal, mudah untuk membuat fungsi yang waktu prosesnya tidak kita ketahui cara menghitungnya. Sebagai contoh pertimbangkan hal berikut:

def recursive (n):
    if 0 == n%2:
        return 1 + recursive(n/2)
    elif 1 == n:
        return 0
    else:
        return recursive(3*n + 1)

Saat ini tidak diketahui apakah fungsi ini selalu didefinisikan dengan baik, apalagi apa itu runtime.

Runtime dari pasangan fungsi tertentu tidak terbatas karena tidak ada yang kembali tanpa memanggil yang lain. Nilai kembali dari aini selalu tergantung pada nilai kembali dari panggilan untuk byang selalu panggilan a... dan yang ini apa yang dikenal sebagai rekursi tak terbatas .

Metode yang jelas adalah menjalankan fungsi dan mengukur berapa lama. Ini hanya memberitahu Anda berapa lama waktu yang dibutuhkan untuk input tertentu. Dan jika Anda tidak tahu sebelumnya bahwa fungsi berakhir, sulit: tidak ada cara mekanis untuk mengetahui apakah fungsi berakhir - itu masalah penghentian , dan itu tidak dapat diputuskan.

Menemukan run time dari suatu fungsi sama-sama tidak dapat diputuskan, oleh teorema Rice . Faktanya, teorema Rice menunjukkan bahwa bahkan memutuskan apakah suatu fungsi berjalan dalam O(f(n))waktu tidak dapat ditentukan.

Jadi yang terbaik yang dapat Anda lakukan secara umum adalah menggunakan kecerdasan manusia Anda (yang, sejauh yang kami tahu, tidak terikat oleh batas-batas mesin Turing) dan mencoba mengenali suatu pola, atau menciptakannya. Cara tipikal untuk menganalisis run time dari suatu fungsi adalah mengubah definisi rekursif fungsi menjadi persamaan rekursif pada run time-nya (atau seperangkat persamaan untuk fungsi rekursif bersama):

T_a(x) = if x ≤ 0 then 1 else T_b(x-1) + T_a(x-1)
T_b(x) = if x ≤ -5 then 1 else T_b(T_a(x-1))

Apa selanjutnya? Anda sekarang memiliki masalah matematika: Anda harus menyelesaikan persamaan fungsional ini. Suatu pendekatan yang sering berhasil adalah mengubah persamaan ini pada fungsi integer menjadi persamaan pada fungsi analitik dan menggunakan kalkulus untuk menyelesaikannya, menafsirkan fungsi T_adan T_bsebagai fungsi yang menghasilkan .

Pada fungsi menghasilkan dan topik matematika diskrit lainnya, saya merekomendasikan buku Matematika Beton , oleh Ronald Graham, Donald Knuth dan Oren Patashnik.

Seperti yang ditunjukkan orang lain, menganalisis rekursi bisa menjadi sangat sulit dengan sangat cepat. Berikut adalah contoh lain dari hal tersebut: http://rosettacode.org/wiki/Mutual_recursion http://en.wikipedia.org/wiki/Hofstadter_afterence#Hofstadter_Female_and_Male_foreences sulit untuk menghitung jawaban dan waktu berjalan untuk ini. Ini karena fungsi-fungsi yang saling rekursif ini memiliki "bentuk yang sulit".

Bagaimanapun, mari kita lihat contoh mudah ini:

http://pramode.net/clojure/2010/05/08/clojure-trampoline/

(declare funa funb)
(defn funa [n]
  (if (= n 0)
    0
    (funb (dec n))))
(defn funb [n]
  (if (= n 0)
    0
    (funa (dec n))))

Mari kita mulai dengan mencoba menghitung funa(m), m > 0:

funa(m) = funb(m - 1) = funa(m - 2) = ... funa(0) or funb(0) = 0 either way.

Run-time adalah:

R(funa(m)) = 1 + R(funb(m - 1)) = 2 + R(funa(m - 2)) = ... m + R(funa(0)) or m + R(funb(0)) = m + 1 steps either way

Sekarang mari kita ambil contoh lain yang sedikit lebih rumit:

Terinspirasi oleh http://planetmath.org/encyclopedia/MutualRecursion.html , yang merupakan bacaan yang bagus dengan sendirinya, mari kita lihat: "" "Angka-angka Fibonacci dapat ditafsirkan melalui rekursi bersama: F (0) = 1 dan G (0 ) = 1, dengan F (n + 1) = F (n) + G (n) dan G (n + 1) = F (n). "" "

Jadi, apa runtime dari F? Kami akan pergi ke arah lain.
Nah, R (F (0)) = 1 = F (0); R (G (0)) = 1 = G (0)
Sekarang R (F (1)) = R (F (0)) + R (G (0)) = F (0) + G (0) = F (1)
...
Tidak sulit untuk melihat bahwa R (F (m)) = F (m) - misalnya jumlah pemanggilan fungsi yang diperlukan untuk menghitung angka Fibonacci pada indeks i sama dengan nilai angka Fibonacci pada indeks i. Ini diasumsikan bahwa menambahkan dua nomor bersama-sama jauh lebih cepat daripada panggilan fungsi. Jika ini tidak terjadi, maka ini benar: R (F (1)) = R (F (0)) + 1 + R (G (0)), dan analisisnya akan lebih rumit, mungkin tanpa solusi bentuk mudah ditutup.

Bentuk tertutup untuk urutan Fibonacci tidak selalu mudah untuk ditemukan kembali, belum lagi beberapa contoh yang lebih rumit.

Hal pertama yang harus dilakukan adalah menunjukkan bahwa fungsi yang telah Anda tentukan berakhir dan yang nilainya tepat. Dalam contoh yang Anda tentukan

int a(int x){
  if (x < = 0)
    return 1010;
  else
    return b(x-1) + a(x-1);
}
int b(int y){
  if (y <= -5)
    return -2;
  else
    return b(a(y-1));
}

bhanya berakhir y <= -5karena jika Anda memasukkan nilai lain maka Anda akan memiliki ketentuan dalam formulir b(a(y-1)). Jika Anda melakukan sedikit lebih berkembang Anda akan melihat bahwa istilah formulir b(a(y-1))akhirnya mengarah ke istilah b(1010)yang mengarah ke istilah b(a(1009))yang lagi mengarah ke istilah tersebut b(1010). Ini berarti Anda tidak dapat memasukkan nilai apa pun ke dalam ayang tidak memuaskan x <= -4karena jika Anda melakukannya Anda berakhir dengan loop tak terbatas di mana nilai yang akan dihitung tergantung pada nilai yang akan dihitung. Jadi pada dasarnya contoh ini memiliki run time yang konstan.

Jadi jawaban sederhananya adalah bahwa tidak ada metode umum untuk menentukan waktu proses fungsi rekursif karena tidak ada prosedur umum yang menentukan apakah fungsi yang didefinisikan secara rekursif berakhir.

Runtime seperti di Big-O?

Itu mudah: O (N) - dengan asumsi ada kondisi terminasi.

Rekursi hanyalah perulangan, dan perulangan sederhana adalah O (N) tidak peduli berapa banyak hal yang Anda lakukan dalam perulangan itu (dan memanggil metode lain hanyalah langkah lain dalam perulangan).

Yang menarik adalah jika Anda memiliki satu loop dalam satu atau lebih metode rekursif. Dalam hal ini Anda akan berakhir dengan semacam kinerja eksponensial (dikalikan dengan O (N) pada setiap melewati metode).