Komplit fact()

Berikut adalah code fact() yang telah lengkap:

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         sub     $sp,$sp,4        #   1. Push return address
         sw      $ra,($sp)
         sub     $sp,$sp,4        #   2. Push caller's frame pointer
         sw      $fp,($sp)
         sub     $sp,$sp,4        #   3. Push register $s1
         sw      $s1,($sp)
         sub     $fp,$sp,0        #   4. $fp = $sp - space_for_variables (==0)
         move    $sp,$fp          #   5. $sp = $fp
         
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         b       epilog    

recurse:                          # else
                                  #  return n*fact(n-1)
         sub     $a0,$s1,1        #     n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine

         mul     $v0,$v0,$s1      # n*fact(n-1)
                            
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         add     $sp,$fp,0        #   2. $sp = $fp + space_for_variables (==0)
         lw      $s1,($sp)        #   3. Pop register $s1
         add     $sp,$sp,4        #          
         lw      $fp,($sp)        #   4. Pop $fp
         add     $sp,$sp,4        #           
         lw      $ra,($sp)        #   5. Pop $ra
         add     $sp,$sp,4        #            
         jr      $ra              #   6. return to caller 

Quest 28: Adakah perbedaan konvensi linkage subroutine yang mengalir rekursif dengan yang tidak?
Jawab: Tidak ada, keduanya sama-sama berjalan dengan cara yang sama, yang spesial dari rekursif adalah dia memanggil dirinya sendiri.

Memanggil Recursive

         . . . . . .

recurse:                          # else
                                  #   return n*fact(n-1);
         sub     $a0,$s1,1        #     argument0 = n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine

         mul     $v0,$v0,$s1      # n*fact(n-1)

epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Rekursi telah diimplementasikan di sini menggunakan: (1) operasi mesin standar yang menggunakan eksekusi, testing dan percabangan. dan (2) runtime stack.

Ini adalah contoh abstraksi tingkat baru yang berada di atas tingkat dasar. Apakah menurut kamu ini adalah ide penting dalam ilmu komputer?

Quest 27: Bahasa pemrograman FORTRAN IV tidak mendukung rekursi. Apakah mungkin untuk membuat program rekursi menggunakan FORTRAN IV?
Jawab: Bisa, FORTRAN memiliki eksekusi yang berurutan, testing dan percabangan, seperti halnya semua bahasa. Untuk menulis sebuah program rekursif maka programmer harus mengalokasikan dan mengelola run-time stack, seperti dalam bahasa assembly. Bahasa modern tingkat tinggi melakukan hal ini secara otomatis.

Selanjutnya dari fact()

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         . . . . . .
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         b       epilog  

recurse:                          # else
                                  #   return n*fact(n-1);
         sub     $a0,$s1,1        #     argument0 = n-1
                       
                                  # subroutine call
                                  #   1. No T registers to push
                                  #   2. Argument is in $a0 
         jal     fact             #   3. Jump and link to subroutine
                                  #
                                  #   value is returned in $v0

         mul      ,  ,    # n*fact(n-1)

epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Percabangan dari if jika $s1 tidak sama dengan 1 atau kurang dari 1, adalah melompat ke symbolic address recurse yang melakukan pekerjaan n*fact(n-1). Dia pertama kali mengerjakan n-1 yang disimpan ke $a0 kemudian baru mengalikan.

Setelah itu dia memanggil fact(), tidak perlu kuatir untuk memanggil ulang karena setiap aktiuvasi akan menggunakan stacknya sendiri-sendiri.

Setelah memanggil fact(), register $v0 memegang return value (nilai hasil) dan register $s1 memegang nilai n.

Body dari fact()

Berikut adalah bagian dari isi subroutine fact().

#  int fact( int n )
#  {
#    if ( n<=1)
#      return 1;
#    else
#      return n*fact(n-1);
#  }
         .text
         .globl  fact
fact:
                                  # prolog        
         . . . . . .
                                  # body of subroutine
         move    $s1,$a0          # save argument in $s1
         li      $t1,1            # get a 1
         bgt     $s1,$t1,recurse  # if ( n<=1)
         li      $v0,1            #   return 1
         
         b        

recurse:                          # else
                                  #   return n*fact(n-1);
         . . . . . . 
epilog:                           # epilog
                                  #   1. Return value is already in $v0        
         . . . . . .
         jr      $ra              #

Argumen yang berada di $a0 diamankan ke register $s1 karena kemungkinan nantinya register $a0 akan berubah. Secara subroutine ini menggunakan $s1 maka $s1 diamankan ke dalam stack saat prolog.

Operasi if di sini bekerja untuk mengecek apakah isi dari argumen $a0 yang sudah dipindah ke $s1 bernilai 1 atau kurang. Jika iya maka dia akan meletakkan nilai 1 ke register $v0 yang nantinya register ini akan digunakan sebagai accumulator. Jika tidak maka cabang lain akan diberlakukan.