.data
towera:	.asciiz "A"
towerb: .asciiz "B"
towerc:	.asciiz "C"
nl:	.asciiz "\n"
numstr:	.asciiz " moves.\n"

inst1:	.asciiz "Move one disc from "
inst2:	.asciiz " to "

	.text
	.globl main



hanoi:		# tower of hanoi procedure
		# lists moves of discs from tower 1 to tower 3 via tower 2
		# arguments: number of discs -> $a0
		#            address of name of tower 1 -> $a1
		#            address of name of tower 2 -> $a2
		#            address of name of tower 3 -> $a3
		# results:   number of moves -> $v0
	bgt $a0, $zero, h_nonzero

	move $v0, $zero
	jr $ra

h_nonzero:
	addi, $sp, $sp, -24	# allocate stack space
	sw $ra, 20($sp)		# push $ra
	sw $a0, 16($sp)		# push $a0
	sw $a1, 12($sp)		# push $a1
	sw $a2, 8($sp)		# push $a2
	sw $a3, 4($sp)		# push $a3

	move $t0, $a3		# set arguments
	move $a3, $a2
	move $a2, $t0
	addi, $a0, $a0, -1
	jal hanoi		# call hanoi procedure

	sw $v0, 0($sp)		# push $v0

	# start print statement

	la $a0, inst1
	li $v0, 4
	syscall # print string

	lw $a0, 12($sp)		# name of tower 1
	syscall			# print string

	la $a0, inst2
	syscall			# print string

	lw $a0, 4($sp)		# name of tower 3
	syscall			# print string

	la $a0, nl
	syscall			# print string

	# end print statement

	lw $a0, 16($sp)		# restore arguments
	lw $a1, 12($sp)
	lw $a2, 8($sp)
	lw $a3, 4($sp)

	move $t0, $a1		# set arguments
	move $a1, $a2
	move $a2, $t0
	addi, $a0, $a0, -1
	jal hanoi		# call hanoi procedure

	lw $t0, 0($sp)		# pop old $v0 (to $t0)

	add $v0, $v0, $t0
	addi $v0, $v0, 1
	lw $ra, 20($sp)		# restore return address
	addi $sp, $sp, 24	# deallocate stack space
	jr $ra



main:	addi $sp, $sp, -4	# allocate stack space
	sw $ra, 0($sp)		# push $ra

	li $a0, 5
	la $a1, towera
	la $a2, towerb
	la $a3, towerc
	jal hanoi		# call hanoi procedure

	move $a0, $v0
	li $v0, 1
	syscall			# print int

	la $a0, numstr
	li $v0, 4
	syscall			# print string

	lw $ra, 0($sp)		# pop $ra
	addi $sp, $sp, 4	# deallocate stack space
	jr $ra			# jump $ra (exit)