Pembuat Kode Lain Bingung dengan Rekursi [duplikat]

Misalkan saya ingin menjumlahkan dua angka tetapi saya hanya dapat menambah dan mengurangi sebanyak 1. Saya dapat menyelesaikan masalah ini dengan beberapa cara termasuk menggunakan rekursi. Ketika saya menambahkan m dan n saya dapat menggunakan definisi Python berikut:

def slowAdd(m, n):
    if n == 0:
       return m
    else:
       return 1 + slowAdd(m, n-1)

Ini sungguh membingungkan saya. Adakah yang bisa menjelaskan cara kerja panggilan balasan terakhir? Bagaimana Python menafsirkan nilai fungsi yang ditentukan saat menambahkannya ke 1?


python recursion return algorithm
person oliver    schedule 30.01.2017    source sumber
comment
Ini bukan nilai dari fungsi yang ditentukan, melainkan nilai kembalian dari pemanggilan fungsi. Apakah itu membantu Anda?   -  person Fred Larson    schedule 31.01.2017
comment
Itu menambahkan apa yang dikembalikan oleh slowAdd(m, n-1). Jadi, jika Anda punya def f(n): return 8 - n dan melakukan 1 + f(1) Anda akan mendapat 8.   -  person juanpa.arrivillaga    schedule 31.01.2017
comment
Baca entri Wikipedia tentang rekursi.   -  person Barmar    schedule 31.01.2017
comment
Apakah saya biasanya tidak perlu menggunakan fungsi loop untuk efek jenis ini?   -  person oliver    schedule 31.01.2017
comment
@Oliver Rekursi adalah jenis loop.   -  person Barmar    schedule 31.01.2017
comment
Tapi saya belum mendefinisikannya seperti itu ..   -  person oliver    schedule 31.01.2017
comment
Rekursi: lihat Rekursi   -  person Fred Larson    schedule 31.01.2017
comment
@Oliver Anda belum mendefinisikan apa seperti itu?   -  person juanpa.arrivillaga    schedule 31.01.2017
comment
@juanpa.arrivillaga putaran. Dia tidak menulis sesuatu yang eksplisit seperti recursion with slowAdd() seperti yang dia lakukan dengan for atau while loop. Dia menanggapi @Barmar, saya kira.   -  person spicypumpkin    schedule 31.01.2017

Jawaban (5)


arrow_upward
5
arrow_downward

Baiklah, mari kita lihat fungsi yang sangat sederhana.

def super_simple_function():
  return 0

Apa yang terjadi jika saya melakukan x = super_simple_function()?

>>> x = super_simple_function()
>>> x
0

Itu karena nilai return fungsinya adalah nol. Jadi ada objek fungsi, yang memberi Anda (mengembalikan) nilai saat dipanggil.

Mari kita lihat fungsi rekursif Anda, baris demi baris. Bayangkan kita memasukkan 2 dan 3 sebagai argumen kita, seperti: slowAdd(2, 3).

Baris 1: def slowAdd(m, n)
Artinya argumen pertama sama dengan m dan kedua, n. Oleh karena itu, dalam kasus kami, m = 2 dan n = 3.

Baris 2: if n == 0
Ini adalah kondisi yang terpicu ketika n equals to 0. Nah, sekarang n = 3 jadi kondisi ini diabaikan.

Baris 3: return m
Karena n tidak sama dengan 0, baris ini diabaikan untuk saat ini; kami akan kembali ke sana.

Baris 4 & 5: else: return 1 + slowAdd(m, n-1)
Ada tiga hal yang terjadi di sini.

  1. Kami menerima nilai pengembalian slowAdd(m, n-1).
  2. Kami menambahkan 1 ke nilai kembalian
  3. Kami mengembalikan jumlah dari #2.

Fungsi ini disebut rekursif karena #1. Seperti yang dapat Anda bayangkan, fungsi ini akan terus memanggil dirinya sendiri hingga n == 0, yang kemudian mengembalikan m, bukan 1 + slowAdd(m, n-1). Dan karena kita mengurangi n sebanyak 1 di setiap rekursi, kita tahu pasti bahwa n pada akhirnya akan sama dengan 0.

Jadi pada dasarnya inilah yang dilakukan fungsi ketika kita meneruskan (2, 3) sebagai argumen:

1st recursion: return 1 + slowAdd(2, 2)
2nd recursion: return 1 + slowAdd(2, 1)
3rd recursion: return 1 + slowAdd(2,0)
4th recursion: return 2            # n is finally 0!

Yang berjumlah 2 + 1 + 1 + 1 = 5.

person spicypumpkin    schedule 30.01.2017

arrow_upward
4
arrow_downward

Anggap saja sebagai mengganti "slowAdd(m, n-1)" dengan ekspresi pengembalian yang benar (baik "m" jika n=0, jika tidak, gantikan "1 + slowAdd(m, n-1)").

Contoh:

slowAdd(5,3)
1 + slowAdd(5, 3-1)
1 + (1 + slowAdd(5, 2-1))
1 + (1 + (1 + slowAdd(5, 1-1)))
1 + (1 + (1 + 5))) // n=0
person jlau    schedule 30.01.2017

arrow_upward
1
arrow_downward

Selama panggilan balik untuk n!=0, fungsi tersebut memanggil dirinya sendiri lagi dengan menambahkan 1 ke nilai ke-n-1. Saya akan menjelaskan ini lebih baik melalui sebuah ilustrasi. Berikut adalah apa yang terjadi dengan fungsi yang Anda panggil:(slowAdd(1,3):)

slowAdd(1,3)
 returns 1+slowAdd(1,2)
           returns 1+slowAdd(1,1)
                     returns 1+slowAdd(1,0)
                               returns 0

Jadi yang terjadi adalah:

 1+3
=1+(1+2)
=1+(1+(1+1))
=1+(1+(1+(1+0)))
person iamnotgoogle    schedule 30.01.2017

arrow_upward
1
arrow_downward

Anda dapat menambahkan pernyataan print di dalam loop dan Anda dapat melihat apa yang terjadi, juga baris if n == 0: dapat ditulis sebagai if not n:

def slowAdd(m, n):
    if not n: return m
    else:
        print('1 + ({}, {})'.format(m, n))
        return 1 + slowAdd(m, n-1)


print(slowAdd(5,5))
1 + (5, 5)
1 + (5, 4)
1 + (5, 3)
1 + (5, 2)
1 + (5, 1)
10
person Simeon Aleksov    schedule 30.01.2017

arrow_upward
1
arrow_downward

ketika kita menjalankan suatu program ada yang kita sebut tumpukan eksekusi

ketika suatu fungsi (A) memanggil fungsi lain (B). program menyimpan konteks fungsi A dalam tumpukan eksekusi sehingga dapat melanjutkan eksekusi fungsi (A) saat menyelesaikan fungsi (B).

konteksnya adalah semua variabel lokal dari fungsi dan instruksi yang tersisa.

misalkan kita memanggil fungsi seperti ini slowAdd(1,9) sebelum memanggil slowAdd(1,9) program akan menyimpan konteksnya sehingga akan menyimpan nilai n=1 saat ini dan nilai m=9 saat ini dan instruksi terakhir yaitu 1+slowAdd(0,9) kemudian akan memanggil slowAdd(0,9) slowAdd(0,9) akan mengembalikan 9 dan program akan kembali ke panggilan pertama ke fungsi tersebut. itu akan memulihkan konteks dan akan menggantikan panggilan dengan nilai yang dikembalikan. 1+slowAdd(0,9) akan menjadi 1+9

person Mohamed Amine Ouali    schedule 30.01.2017