# This program implements the fibonacci numbers, defined doubly recursively:
#
#  f(n) = f(n-1) + f(n-2)
#  f(1) = 1
#  f(0) = 1

### The main program prompts for a value to call f with and prints the result.
### This program is different from the fibonacci.s program because it uses 
### real system stack.
	
# Written by Scott D. Anderson, 2/9/98

	.data
	.align 2
prompt:	.asciiz "\nPlease input a value: "
ans:	.asciiz "The answer is: "
nl:	.asciiz "\n"


	.text
	.globl main
main:	addi $sp,$sp,-4		# adjust sp
	sw $ra 0($sp)		# save return address

	li $v0 4
	la $a0 prompt		# print prompt
	syscall
	
	li $v0 5		# read integer
	syscall

	move $a0 $v0		# load arg
	jal fibo
	
	move $t0 $v0		# save result
	li $v0 4		# code to print string
	la $a0 ans
	syscall
	li $v0 1		# code to print integer
	move $a0 $t0		# retrieve result
	syscall
	li $v0 4		# code to print string (final newline)
	la $a0 nl
	syscall

	lw $ra 0($sp)		# restore return address
	addi $sp,$sp,4		# restore SP
	jr $ra			# done

### 
	
# This is the fibonacci subroutine.  As with all functions, 
# it gets its first (only) arg in $a0 and returns its value in $v0.

fibo:	li $t0 1
	blt $t0 $a0 recur	# branch to recursive part if 1<n
	li $v0 1		# otherwise, our value is 1
	jr $ra
	
recur:	subu $sp $sp 12		# push -- adjust sp for three elements
	sw $ra 0($sp)		# push -- store RA
	sw $a0 4($sp)		# push -- store n

	addi $a0 $a0 -1		# compute n-1
	jal fibo		# first recursive call
	
	sw $v0 8($sp)		# push -- store value of f(n-1)

	lw $a0 4($sp)		# pop -- get n back
	addi $a0 $a0 -2		# compute n-2
	jal fibo		# second recursive call

	lw $t0 8($sp)		# pop -- get f(n-1) back into temp
	add $v0 $v0 $t0		# our value is f(n-1) + f(n-2)

	lw $ra 0($sp)		# retrieve RA
	addu $sp $sp 12		# restore stack pointer
	jr $ra