dpawson
Posts: 129
Joined: Mon Nov 14, 2011 5:05 pm
Contact: Website

recursion... in asm?

Mon Jun 11, 2012 2:53 pm

Tail recursion, in assembler?
E.g. given...

Code: Select all

def mymod(n):
    if (n < 10):
               return n
    return mymod(n - 10)
What might the asm look like?

Any pecularities or is is straightforward?
Not something I'd thought of before.
TIA

godFather89
Posts: 150
Joined: Fri May 18, 2012 9:40 am
Location: Timisoara, RO

Re: recursion... in asm?

Mon Jun 11, 2012 3:09 pm

Not sure of arm asm syntax but of course it's possible (using equivalent for call and ret).

User avatar
rurwin
Forum Moderator
Forum Moderator
Posts: 4258
Joined: Mon Jan 09, 2012 3:16 pm
Contact: Website

Re: recursion... in asm?

Mon Jun 11, 2012 3:20 pm

Tail recursion is a special case. You do not need to use any of the local variables again and the only time you will be passing this way again is in a cascade of Returns heading towards the original caller.

Therefore tail recursion looks like a jump instruction preceeded by code to set the local variables as required for the new call. Contrary to normal recursion there will be exactly one call and one return. The return will be the one where you escape from the recursion.

Code: Select all

def mymod(n):
/* Assembler sets up the stack frame here */
loop:
    if (n < 10):
               /* Assembler tears down stack frame here, or jumps to the end of the function and does it there */
               return n
    n = n - 10;
    goto loop
The assembler will be a little complicated by having to avoid all the fiddling about setting the stack up at the beginning. You probably want to loop back to just after that.

Return to “Advanced users”