![[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.





| Blogs > EsX_Raptor |
|
EsX_Raptor
United States2802 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 States2802 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 States12816 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 States3727 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 States2802 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. | ||
| ||
SOOP
SC2 Kevin Scrim 4v4
ByuN vs RogueLIVE!
IntoTheiNu
FanTaSy93
Maru
Rex36
ByuN (SOOP)
SHIN
soO33
herO (SOOP)
Rogue
Classic
[ Submit Event ] |
|
|
Replay Cast
Monday Night Weeklies
PiGosaur Cup
The PondCast
OSC
Replay Cast
GSL
Patches Events
OSC
Replay Cast
[ Show More ] KCM Race Survival
RSL Revival
BSL
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
BSL
Bonyth vs Doodle
Kyrie vs Jimin
WardiTV Weekly
|
|
|