EPT![[image loading]](http://img297.imageshack.us/img297/710/factorial.jpg)
But I heard that it is also possible to implement that same thing, but using a stack.
I just want to hear what you guys think would be the way to do it, or how to approach it, 'cause I spent the entire day today trying to figure out how.
Stack vs Recursion
| Blogs > EsX_Raptor |
|
EsX_Raptor
United States2801 Posts
But I heard that it is also possible to implement that same thing, but using a stack. I just want to hear what you guys think would be the way to do it, or how to approach it, 'cause I spent the entire day today trying to figure out how. | ||
|
Divinek
Canada4045 Posts
| ||
|
BottleAbuser
Korea (South)1888 Posts
Here's an explicit stack example (Java noob here, sorry): int factorial(int n){ Stack s = new Stack(); for(int i=1; i<=n;i++){ s.push(i); } int result = 1; while(!s.isEmpty()){ result*=s.pop(); } return result; } | ||
cgrinker
United States3824 Posts
Is it a trick question? the recursive function is computed on the stack (just like everything else) when its compiled down to x86. Are you sure you aren't supposed to be doing your assingment in 8086 op codes? | ||
|
EsX_Raptor
United States2801 Posts
(edit: for example, what would I do when I need to implement a naturally recursive function in FORTRAN which doesn't allow recursion) In C++, I actually made the stack myself and I just push, pop and top stuff from it. I'll do what you said cgrinker, brb. | ||
|
haduken
Australia8267 Posts
Recursive functions make implied use of the stack by storing auto variables, function heads and other infos. If you are talking about computing models then stack is recursive by its own defination (I could be wrong here). | ||
|
cgrinker
United States3824 Posts
;Factorial using recursion ;x is the input ADD AX, x ADD BX, x fact; begin MUL BX, AX SUB AX, 1 CMP AX, 1 JNZ fact NOP HLT | ||
|
cgrinker
United States3824 Posts
| ||
|
prOxi.swAMi
Australia3091 Posts
| ||
|
imDerek
United States1944 Posts
| ||
|
evanthebouncy!
United States12796 Posts
It's the tower of Hannoi: #$s1 saves n number #$s2 saves source #$s3 saves dest #$s4 saves help #$ra saves return_address via JAL .data n: .word 30 source: .asciiz "A" destination: .asciiz "B" helper: .asciiz "C" newline: .asciiz "\n" .text main: lw $s1, n la $s2, source la $s3, destination la $s4, helper la $s5, newline jal loop j done loop: addi $sp, $sp, -20 #pull down stack and save junks sw $ra, 0($sp) #save return address first sw $s1, 4($sp) #push n to stack sw $s2, 8($sp) #push source to stack sw $s3, 12($sp) #push dest to stack sw $s4, 16($sp) #push helper stack jal test #see if we reached 0, if no, continue, if yes, go to end_loop addi $s1, $s1, -1 #decrease n by 1 move $t0, $s3 #swap dest with help move $s3, $s4 move $s4, $t0 jal loop #loop again, send it downward to the tree li $v0, 4 #print stuff lw $a0, 8($sp) syscall lw $a0, 12($sp) syscall addi $a0, $s5, 0 syscall lw $s2, 8($sp) #load up the source/helper, swap them lw $s3, 12($sp) lw $s4, 16($sp) move $t0, $s2 move $s2, $s4 move $s4, $t0 jal loop #going down again. end_loop: #get the register return address, and return it lw $ra, 0($sp) #reload register lw $s1, 4($sp) #reload n to return to upper level addi $sp, $sp, 20 #pop stacks jr $ra #return to what called it test: beq $s1, $zero, is_zero #if it is 0, go to is_zero option jr $ra #if it's not 0, simply return to deepen the tree is_zero: j end_loop #jump to end of the loop done: li $v0, 10 syscall | ||
|
tec27
United States3690 Posts
On April 24 2009 15:20 cgrinker wrote: Do you have direct control of the stack in C++? We do it when we code in assembly (Jasmin) put the idea of recursion is that when your function calls itself every call is pushed onto the stack so that once you reach your base case you start popping values down the stack. Is it a trick question? the recursive function is computed on the stack (just like everything else) when its compiled down to x86. Are you sure you aren't supposed to be doing your assingment in 8086 op codes? You're confusing "the stack" with "a stack". A stack, as I'm sure you probably realize is just a type of data structure with a LIFO interface. "The stack" that you speak of is a specific usage of that data structure for storing info such as function parameters/return addresses. So while when you implement this algorithm using a lower level language like assembly, it may be easier to use "the stack" as the stack in question, higher level languages would typically create a new object of a stack class and use that. | ||
|
Cambium
United States16368 Posts
Stack stach = new Stack(); for( int i = 0; i < n; i ++ ) stach.push( i ); int result = 1; while( !stach.empty() ){ result * = (int) stach.pop(); } return result; } | ||
|
Cambium
United States16368 Posts
| ||
|
EsX_Raptor
United States2801 Posts
trying to control THE stack would be something really complex actually, and im not yet into that level of programming >.< i'll try to implement a quicksort using a stack. | ||
| ||
