7163313950

5. Rekurencja

5.1.    Funkcje rekurencyjne muszą być tak konstruowane, aby mogły wywoływać same siebie, dlatego należy:

a)    w ramce stosu zachować stan rejestrów, zgodnie z odpowiedzialnością wywołującego

b)    w ramce stosu zachować stan rejestrów, zgodnie z odpowiedzialnością wywoływanego

c)    w ramce stosu przechowywać zmienne lokalne

5.2.    Przykładowa funkcja rekurencyjna wyznaczająca silnię

a)    zapis w pseudokodzie

int fact(int X) { int result;

if (x == 1) return(l); result = X * fact(X-l); return(X);

>

b)    Zmienna lokalna X jest jednocześnie argumentem funkcji, więc należy ją zachować w ramce stosu dla potrzeb wykonania mnożenia przez zwrócony rezultat.

5.3.    Zadanie 4

a) Wprowadzić kod programu .text

main:	subu $sp, $sp, 24 sw $ra, 20($sp)	^#	utworzyć standardową ramkę
	li $a0, 6	#	wywołać factorial(6)
	jal factorial	#	rezultat jest w $v0,
	move $a0, $v0 li $v0, 1 syscall		wydrukować go
	li $v0, 10 syscall	#	exit
factorial:	subu $sp, $sp, 24	#	utworzyć standardową ramkę 24-bajtową
	sw $ra, 20($sp)	#	zachować adres powrotny
		#	bo będzie wywołanie rekurencyjne.
	sw $a0, 0($sp)	#	zachować argument wywołania,
		#	bo będzie potrzebny do mnożenia.
	bgt $a0, 1, notbasecase		# if arg > 1, not the base case, skip
basecase:	li $v0, 1	#	przypadek bazowy: fact(l) = 1
	b factreturn	#	zwrócić rezultat.
notbasecase:	subi $a0, $a0, 1	#	przypadek niebazowy: argument funkcji zmniejszyć o 1
	jal factorial	#	i wywołać funkcję factorial
		#	rezultat jest w $v0
	lw $a0, 0,($sp)	#	pobrać oryginalny argument z ramki stosu
	mulo $v0, $a0, $v0	#	result = argument * factorial(argument - 1)
factreturn:	: lw $ra, 20($sp)	#	odtworzyć adres powrotny
	addu $sp, $sp, 24	#	zniszczyć ramkę
	jr $ra	#	wrócić do wywołującego (rezultat w $v0)

b) Przeanalizować program, podać asemblacji i wykonać.

c) Wykonać program krokowo, analizując stan stosu, ramki dla kolejnych wywołań rekurencyjnych, kolejne operacje mulo.