How would a recursive fibonacci be implemented in MIPS? I need general advice...
Posted by Electronic_Pace_6234@reddit | learnprogramming | View on Reddit | 10 comments
now to be fair im kinda very sleep deprived lately so my brain aint working as it usually does, but I worked on it yesterday for at least 2 hours and couldnt figure it out. Any tips on how to get at the solution? Thinking about it yesterday, since the pc works sequentially it would have to i guess do the n-1 recursion first and then switch to the other one. And thus either back and forth or in another manner. But given that it has to be recursive how would this back and forth be done without an infinite loop or something...
Feeling_Temporary625@reddit
Stack management is gonna be your best friend here - you basically need to push your return address and current n value before each recursive call, then pop them back when you return
The trick is using `$ra` to jump back to where you came from and making sure you don't overwrite it when you make the next recursive call
HashDefTrueFalse@reddit
There's an explanation of some recursive assembly code in my comment history somewhere if you search it. It's not MIPS (IIRC it's arm64) but it might help you in some way. I can't remember if it's Fibonacci or factorial. You're just doing whatever prologue/epilogue you need to for your calling convention, then jumping to the start of the function with the right values in registers or saved onto the stack, essentially.
lurgi@reddit
Do you know how to call a function in MIPS? Do you know how to call a function and then call another function? Can you then combine the results of those two function calls?
That's all a recursive function is, except that you are calling yourself instead of some other function. There is no difference between
and
Electronic_Pace_6234@reddit (OP)
ive already implemented factorial. Its not recursion by itself thats throwing me off, its the nested recursion. how do i reroute the return address properly...i need a type of framework for solving this. its really messing with my head.
lurgi@reddit
Its.
Just.
A.
Function.
Call.
That's the point. If you can call a function and return properly then you can do this. There is nothing special about the function being recursive.
Electronic_Pace_6234@reddit (OP)
Only you need to manage the return address so that the recursion doesnt break. easy to do with a normal recursion like factorial, but here its nested, and one recursive call depends on the other one.
lurgi@reddit
You need to manage the return address when you call any function.
Electronic_Pace_6234@reddit (OP)
sure, but the unwinding is defined by the part after the return address and i dont see how this should unwind given that its 2 recursive runs that have to happen and they depend on each other. . I think maybe i should try a simple deduction from the fib algorithm itself.
teraflop@reddit
As long as you make each of the individual function calls correctly, it will "just work" without you having to do anything else.
If you have an algorithm that looks like this in pseudocode:
then the first recursive call will save a return address that continues on line 3, and the second call will save a return address that continues on line 4.
As the parent commenter said, this is no different from any other function call. The nested recursive calls don't "depend on each other". The outer call depends on the results of the inner calls, but the inner calls don't care about that.
AutoModerator@reddit
To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.
I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.