Lucas MIPS

#
# La suite de Lucas est definie recursivement comme :
#
# Lucas(0) = 1
# Lucas(1) = 3
# ...
# Lucas(n) = Lucas(n-1) + Lucas(n-2)
#

main:
	addiu $sp, $sp, -4        # deplacement du pointeur de pile -4
	sw $ra, 0($sp)            # stockage de l'adresse de retour dans la pile

	li $a0, 3                 # le registre $a0 est utilise pour le passage en parametre

	jal lucas                 # appel de lucas

	lw $ra, 0($sp)            # chargement de l'adresse de retour
	addiu $sp, $sp, 4         # deplacement du pointeur de pile a sa position initial

	jr $ra

lucas:
	li $v0, 1
	bgtz $a0, is_one          # on regarde si $a0 > 0, si c'est le cas on test le second cas de base en branchant à is_one
	jr $ra                    # sinon c'est fini car lucas(0) == 1

is_one:
	li $v0, 3
	li $t0, 1                 # on charge la valeur 1 dans le registre $t0 afin de faire une comparaison avec $a0
	bne $t0, $a0, lucas_gen   # si $a0 == $t0 alors $a0 == 1 donc nous somme dans le second cas de base (lucas(1) == 3) donc c'est fini
	jr $ra                    # sinon on branche a lucas_gen car nous ne somme dans aucun des cas de base

lucas_gen:
	addiu $sp, $sp, -12       # deplacement du pointeur de pile de -12
	sw $ra, 0($sp)            # on enregistre l'adresse de retour dans la pile avec un offset de 0
	sw $a0, 4($sp)            # on enregistre la valeur de $a0 dans la pile avec un offset de 4

	addiu $a0, $a0, -1        # on calcul la valeur pour l'appel récursif 1 lucas($a0-1)
	jal lucas                 # appel recursif 1

	sw $v0, 8($sp)            # on sauve la valeur de retour du premier appel avec un offset de 8

	lw $a0, 4($sp)            # on charge la valeur de $a0 avant le premier appel
	addiu $a0, $a0, -2        # on calcul la valeur pour l'appel recursif 2 lucas($a0 -2)
	jal lucas                 # appel recursif 2

	lw $t1, 8($sp)            # on charge la valeur de retour de l'appel rec. 1 dans $t1
	add $v0, $v0, $t1         # on additionne $v0 (valeur de l'appel rec 2) et $t1 (valeur de l'appel rec. 1) et on sauve le resultat dans $v0

	lw $ra, 0($sp)            # on charge l'adresse de retour depuis la pile (offset 0)
	addiu $sp, $sp, 12        # on replace le pointeur de pile a sa position initial

	jr $ra