[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home] [volume] [parte]


Capitolo 559.   Esempi di funzioni ricorsive

In questo capitolo vengono mostrati alcuni esempi molto semplici in cui si applica la ricorsione, adatti alla compilazione con GNU AS e NASM.

559.1   Elevamento a potenza

Viene proposta una soluzione ricorsiva del problema dell'elevamento a potenza. In pratica, xy è pari a x·x(y-1), ma in particolare: se x è pari a zero, il risultato è zero; altrimenti, se y è pari a zero, il risultato è uno.

All'interno della funzione f_pwr viene riservato lo spazio per una sola variabile locale, che serve a conservare il valore di EAX, per poi recuperarlo quando si ripristinano tutti i registri, prima della conclusione della funzione stessa.

# op1 ^ op2
#
.section .data
op1:    .int    3
op2:    .int    4
#
.section .text
.globl _start
#
# Main.
#
_start:
    mov   op1, %esi        # Base.
    mov   op2, %edi        # Esponente.
bp1:
    push  %edi             # f_pwr (ESI, EDI) ==> EAX
    push  %esi             #
    call  f_pwr            #
    add   $8, %esp         #
bp2:
    mov   %eax, %ebx       # Restituisce il valore della potenza,
    mov   $1, %eax         # ammesso che sia abbastanza piccolo
    int   $0x80            # da poter essere rappresentato come
                           # valore di uscita.
#
# Potenza di due numeri interi senza segno.
# f_pwr (a, b) ==> EAX
# EAX = a ^ b
#
f_pwr:
    enter $4, $0
    pusha
    #
    mov   8(%ebp), %esi    # Base.
    mov   12(%ebp), %edi   # Esponente.
    #
    cmp   $0, %esi         # Se la base è pari a 0, restituisce 0.
    jz    f_pwr_end_0      #
    #
    cmp   $0, %edi         # Se l'esponente è pari a 0, restituisce 1.
    jz    f_pwr_end_1      #
    #
    dec   %edi             # Riduce l'esponente di una unità.
    push  %edi             # f_pwr (ESI, EDI) ==> EAX
    push  %esi             #
    call  f_pwr            #
    add   $8, %esp         #
    mul   %esi             # EDX:EAX = EAX*ESI
    mov   %eax, -4(%ebp)   # Salva il risultato.
    jmp   f_pwr_end_X      # Conclude la funzione.
    #
f_pwr_end_0:
    popa                   # Conclude la funzione con EAX = 0.
    mov $0, %eax           #
    leave                  #
    ret                    #
f_pwr_end_1:
    popa                   # Conclude la funzione con EAX = 1.
    mov $1, %eax           #
    leave                  #
    ret                    #
f_pwr_end_X:
    popa                   # Conclude la funzione con EAX pari
    mov -4(%ebp), %eax     # al valore salvato nella variabile
    leave                  # locale.
    ret                    #
; op1 ^ op2
;
section .data
op1:    dd      3
op2:    dd      4
;
section .text
global _start
;
; Main.
;
_start:
    mov   esi, [op1]       ; Base.
    mov   edi, [op2]       ; Esponente.
bp1:
    push  edi              ; f_pwr (ESI, EDI) ==> EAX
    push  esi              ;
    call  f_pwr            ;
    add   esp, 8           ;
bp2:
    mov   ebx, eax         ; Restituisce il valore della potenza,
    mov   eax, 1           ; ammesso che sia abbastanza piccolo
    int   0x80             ; da poter essere rappresentato come
                           ; valore di uscita.
;
; Potenza di due numeri interi senza segno.
; f_pwr (a, b) ==> EAX
; EAX = a ^ b
;
f_pwr:
    enter 4,0
    pusha
    ;
    mov   esi, [ebp+8]     ; Base.
    mov   edi, [ebp+12]    ; Esponente.
    ;
    cmp   esi, 0           ; Se la base è pari a 0, restituisce 0.
    jz    f_pwr_end_0      ;
    ;
    cmp   edi, 0           ; Se l'esponente è pari a 0, restituisce 1.
    jz    f_pwr_end_1      ;
    ;
    dec   edi              ; Riduce l'esponente di una unità.
    push  edi              ; f_pwr (ESI, EDI) ==> EAX
    push  esi              ;
    call  f_pwr            ;
    add   esp, 8           ;
    mul   esi              ; EDX:EAX = EAX*ESI
    mov   [ebp-4], eax     ; Salva il risultato.
    jmp   f_pwr_end_X      ; Conclude la funzione.
    ;
f_pwr_end_0:
    popa                   ; Conclude la funzione con EAX = 0.
    mov eax, 0             ;
    leave                  ;
    ret                    ;
f_pwr_end_1:
    popa                   ; Conclude la funzione con EAX = 1.
    mov eax, 1             ;
    leave                  ;
    ret                    ;
f_pwr_end_X:
    popa                   ; Conclude la funzione con EAX pari
    mov eax, [ebp-4]       ; al valore salvato nella variabile
    leave                  ; locale.
    ret                    ;

559.2   Fattoriale

Viene proposta una soluzione ricorsiva del problema del fattoriale. In pratica, x! è pari a x·(x-1)!, ma in particolare: se x è pari a 1, il risultato è uno.

All'interno della funzione f_fact viene riservato lo spazio per una sola variabile locale, che serve a conservare il valore di EAX, per poi recuperarlo quando si ripristinano tutti i registri, prima della conclusione della funzione stessa.

# op1!
#
.section .data
op1:    .int    5
#
.section .text
.globl _start
#
# Main.
#
_start:
    mov   op1, %esi        # ESI contiene il valore di cui si vuole
                           # calcolare il fattoriale.
bp1:
    push  %esi             # f_fact (ESI) ==> EAX
    call  f_fact           #
    add   $4, %esp         #
bp2:
    mov   %eax, %ebx       # Restituisce il valore del fattoriale,
    mov   $1, %eax         # ammesso che sia abbastanza piccolo
    int   $0x80            # da poter essere rappresentato come
                           # valore di uscita.
#
# Fattoriale di un numero senza segno.
# f_fatt (a) ==> EAX
# EAX = a!
#
f_fact:
    enter $4, $0
    pusha
    #
    mov   8(%ebp), %edi    # Valore di cui calcolare il fattoriale.
    #
    cmp   $1, %edi         # Il fattoriale di 1 è 1.
    jz    f_fact_end_1     #
    #
    mov   %edi, %esi       # ESI contiene il valore di cui si vuole
    dec   %esi             # il fattoriale, ridotto di una unità.
    #
    push  %esi             # f_fact (ESI) ==> EAX
    call  f_fact           #
    add   $4, %esp         #
    mul   %edi             # EDX:EAX = EAX*EDI
    mov   %eax, -4(%ebp)   # Salva il risultato.
    jmp   f_fact_end_X     # Conclude la funzione.
    #
f_fact_end_1:
    popa                   # Conclude la funzione con EAX = 1.
    mov $1, %eax           #
    leave                  #
    ret                    #
f_fact_end_X:
    popa                   # Conclude la funzione con EAX pari
    mov -4(%ebp), %eax     # al valore salvato nella variabile
    leave                  # locale.
    ret                    #
; op1!
;
section .data
op1:    dd      5
;
section .text
global _start
;
; Main.
;
_start:
    mov   esi, [op1]       ; ESI contiene il valore di cui si vuole
                           ; calcolare il fattoriale.
bp1:
    push  esi              ; f_fact (ESI) ==> EAX
    call  f_fact           ;
    add   esp, 4           ;
bp2:
    mov   ebx, eax         ; Restituisce il valore del fattoriale,
    mov   eax, 1           ; ammesso che sia abbastanza piccolo
    int   0x80             ; da poter essere rappresentato come
                           ; valore di uscita.
;
; Fattoriale di un numero senza segno.
; f_fatt (a) ==> EAX
; EAX = a!
;
f_fact:
    enter 4,0
    pusha
    ;
    mov   edi, [ebp+8]     ; Valore di cui calcolare il fattoriale.
    ;
    cmp   edi, 1           ; Il fattoriale di 1 è 1.
    jz    f_fact_end_1     ;
    ;
    mov   esi, edi         ; ESI contiene il valore di cui si vuole
    dec   esi              ; il fattoriale, ridotto di una unità.
    ;
    push  esi              ; f_fact (ESI) ==> EAX
    call  f_fact           ;
    add   esp, 4           ;
    mul   edi              ; EDX:EAX = EAX*EDI
    mov   [ebp-4], eax     ; Salva il risultato.
    jmp   f_fact_end_X     ; Conclude la funzione.
    ;
f_fact_end_1:
    popa                   ; Conclude la funzione con EAX = 1.
    mov eax, 1             ;
    leave                  ;
    ret                    ;
f_fact_end_X:
    popa                   ; Conclude la funzione con EAX pari
    mov eax, [ebp-4]       ; al valore salvato nella variabile
    leave                  ; locale.
    ret                    ;

Appunti di informatica libera 2008 --- Copyright © 2000-2008 Daniele Giacomini -- <appunti2 (ad) gmail·com>


Dovrebbe essere possibile fare riferimento a questa pagina anche con il nome esempi_di_funzioni_ricorsive.htm

[successivo] [precedente] [inizio] [fine] [indice generale] [indice ridotto] [indice analitico] [home]

Valid ISO-HTML!

CSS validator!

Gjlg Metamotore e Web Directory