Printing list in MIPS recursion

Question

Currently, I am working with MIPS, and I was wondering what modifications should I make to following code(recursive function to print list):

printList:
   addi $sp, $sp, -8
   sw $ra, 0($sp)
   beqz $a0, endRec
   lw $t0, 0($a0)
   sw $t0, 4($sp)
   lw $a0, 4($a0)
   jal printList
   lw $a0, 4($sp)
   li $v0, 1
   syscall
   la $a0, str
   li $v0, 4
   syscall
endRec:
   lw $ra, 0($sp)
   addi $sp, $sp, 8
   jr $ra

such that it prints list in "normal" order(for example if I am adding elements on the end, 1 2 3, I want it to print it like that and not like 3 2 1). NOTE: str is blanco defined in data segment. I also know that I could do reverse list and then call that function, but is there easier way?

Do you know how this code works? – Erik Eidt Mar 20 '22 at 21:33 — Erik Eidt, Mar 20 '22 at 21:33

score 2 · Accepted Answer · answered Mar 20 '22 at 22:20

2

Though you're working in MIPS, this is not really a MIPS problem, it is a general problem of recursion.

In recursion, let's say we have:

recursiveFunction (...) {
    if condition then exit

    // do some work #1

    recursiveFunction (...);

    // do some other work #2
}

The work that is done in the section tagged #1 will happen before the recursion, e.g. on the recursive descent — in some sense this happens forwards.

The work that is done in the section tagged #2 will happen after the recursion, e.g. on the unwinding of the recursion — in some sense this happens backwards.

If you put the printing in section #2, the list will come out backwards. If you put the printing in section #1, the list will come out forwards.

answered Mar 20 '22 at 22:20

Erik Eidt

23,049
2
29
53

OK, but that means I won't have anything is section #2 right(because I set print in #1)? I mean that is still regular recursion right? – Trevor Mar 20 '22 at 22:39
1

It is still recursion, since it is calling itself. – Erik Eidt Mar 20 '22 at 22:47
1

@Trevor: Right. Recursion is a useless over-complication for a linked list in forwards order; a loop would be much easier to write and more efficient. Recursion is only helpful for traversing a binary tree. Or for printing the list backwards like you're doing, effectively making a backwards array of pointers to nodes on the stack and then looping through that as you return from the recursion. Forwards order is trivial and doesn't need any extra storage, and the recursive implementation becomes tail-recursion which you could very easily optimize down to just a loop. – Peter Cordes Mar 20 '22 at 23:06

Printing list in MIPS recursion

1 Answers1

Linked