• Log InLog In
  • Register
Liquid`
Team Liquid Liquipedia
EST 08:25
CET 14:25
KST 22:25
  • Home
  • Forum
  • Calendar
  • Streams
  • Liquipedia
  • Features
  • Store
  • EPT
  • TL+
  • StarCraft 2
  • Brood War
  • Smash
  • Heroes
  • Counter-Strike
  • Overwatch
  • Liquibet
  • Fantasy StarCraft
  • TLPD
  • StarCraft 2
  • Brood War
  • Blogs
Forum Sidebar
Events/Features
News
Featured News
[ASL22] Finals Preview: Sweet Victory!12[ASL22] Ro4 Preview: Mirror Mirror6[ASL22] Ro8 Preview: Within Reach5[ASL22] Ro8 Preview: In A Tizzy11[ASL22] Ro16 Preview: Holy Diver5
Community News
Dark completes military service, returns to SC212[BSL23] RO16 Group Stage20Weekly Cups (Nov 2-8): herO back on top?2Weekly Cups (Oct 26 - Nov 1): MaxPax, herO, Solar win0Weekly Cups (October 19-25): Clem triples first in 5.0.175
StarCraft 2
General
Dark completes military service, returns to SC2 No more SC2 streamers on team liquid? Serral's getting trashed by New Catsle's Mind Weekly Cups (Nov 2-8): herO back on top? Liquibets sc2 season 30
Tourneys
Sparkling Tuna Cup - Weekly Open Tournament Sea Duckling Open (Global, Bronze-Diamond) Dark returns! GSL CK #7 4v4 Team Battle (Nov 19) soO & FanTaSy return! SC2 Kevin Scrim 4v4 (Nov 16) RSL goes to London! 2026 Offline Finals Nov 21-22
Strategy
[H] ZvP Mid-Late Game: Stalkers Collossi HT
Custom Maps
[G] How to playtest arcade maps Starcraft 2 Advance [D] the control group Simple Questions/Answers
External Content
Mutation # 552 Secret Storm The PondCast: SC2 News & Results Mutation # 551 Robotic Revival Mutation # 550 Graveyard Shift
Brood War
General
BW General Discussion BGH Auto Balance -> http://bghmmr.eu/ Shield Battery Server New Patch Top Players of October 2026 (EBPD Rankings) List of top players active on ShieldBattery
Tourneys
[$1250] International ShieldBattery League 2v2v2v2 Tournament Stage 2: Players [BSL23] Ro16 Group C - Sunday 21:00 CET [Megathread] Daily Proleagues
Strategy
Pluto's TvP 5Marine 2Medic Push Simple Questions, Simple Answers Infested Terran strategies in 2026 Nuke strategy worked in K-League 2026-11-09
Other Games
General Games
Free Space RTS Game, optimised f. Phone/Tablet etc Stormgate/Frost Giant Megathread Nintendo Switch Thread List of Game Threads The PlayStation 5
Dota 2
League of Legends
[TL LoL EUW IHs] Teemo shall perish
Heroes of the Storm
Heroes of the Storm 2.0
Hearthstone
Deck construction bug
TL Mafia
TL Mafia Community Thread
Community
General
US Politics Mega-thread Artificial Intelligence Thread Things Aren’t Peaceful in Palestine Trading/Investing Thread European Politico-economics QA Mega-thread
Fan Clubs
Fan Club Resource Thread Reynor Fan Club The Flash Fan Club
Media & Entertainment
Movie Discussion! Anime Discussion Thread [Manga] One Piece
Sports
Football (Soccer) Thread TeamLiquid Health and Fitness Initiative For 2023 MLB/Baseball 2023
World Cup 2022
Tech Support
Computer Build, Upgrade & Buying Resource Thread
TL Community
The Automated Ban List Recent Gifted Posts
Blogs
The time I organised my…
AssyrianKing
Why I built Repalyzer (1.1.…
BlueStar
Innovate or Game Over?
TrAiDoS
ShieldBattery on Mac
Kraekkling
Can Bots Beat Pros?? Starcr…
namkraft
Customize Sidebar...

Website Feedback

Closed Threads



Active: 6901 users

Stack vs Recursion

Blogs > EsX_Raptor
Post a Reply
EsX_Raptor
Profile Blog Joined February 2008
United States2802 Posts
April 24 2009 06:15 GMT
#1
Alright, we all know what a recursive function is (C++ example):

[image loading]


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
Profile Blog Joined November 2006
Canada4045 Posts
April 24 2009 06:17 GMT
#2
Well if you understand what a stackframe is in java and how recursion works there,it's the same idea
Never attribute to malice that which can be adequately explained by stupidity.
Oh goodness me, FOX tv where do you get your sight? Can't you keep track, the puck is black. That's why the ice is white.
BottleAbuser
Profile Blog Joined December 2007
Korea (South)1888 Posts
Last Edited: 2009-04-24 06:22:52
April 24 2009 06:19 GMT
#3
Recursion is implemented with a stack in most computers, actually.

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;
}
Compilers are like boyfriends, you miss a period and they go crazy on you.
cgrinker
Profile Blog Joined December 2007
United States3824 Posts
April 24 2009 06:20 GMT
#4
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?
EsX_Raptor
Profile Blog Joined February 2008
United States2802 Posts
Last Edited: 2009-04-24 06:33:55
April 24 2009 06:32 GMT
#5
its not an assignment, I just want to know how to program recursive functions using stacks instead.
(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
Profile Blog Joined April 2003
Australia8267 Posts
April 24 2009 06:39 GMT
#6
??? weird question.

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).
Rillanon.au
cgrinker
Profile Blog Joined December 2007
United States3824 Posts
April 24 2009 06:50 GMT
#7
in x86!

;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
Profile Blog Joined December 2007
United States3824 Posts
April 24 2009 06:52 GMT
#8
If you can't do function calls then you are going to have to use a pointer function like JMP (jump) or, god forbid some kind of goto thing. Then you need to compare the value to see if you have reached your base case. Its kinda backwards in assembly.
prOxi.swAMi
Profile Blog Joined November 2004
Australia3091 Posts
April 24 2009 06:53 GMT
#9
Recursive functions, a function calling itself, IS using a stack...
Oh no
imDerek
Profile Blog Joined August 2007
United States1944 Posts
April 24 2009 06:57 GMT
#10
all procedure calls are using a stack to keep track of frames
Least favorite progamers: Leta, Zero, Mind, Shine, free, really <-- newly added
evanthebouncy!
Profile Blog Joined June 2006
United States12816 Posts
April 24 2009 07:00 GMT
#11
If you want to do it with stack consider this code in MIPS:
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
Life is run, it is dance, it is fast, passionate and BAM!, you dance and sing and booze while you can for now is the time and time is mine. Smile and laugh when still can for now is the time and soon you die!
tec27
Profile Blog Joined June 2004
United States3727 Posts
April 24 2009 07:28 GMT
#12
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.
Can you jam with the console cowboys in cyberspace?
Cambium
Profile Blog Joined June 2004
United States16368 Posts
Last Edited: 2009-04-24 07:53:19
April 24 2009 07:52 GMT
#13
int factorial( int n ) {
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;
}
When you want something, all the universe conspires in helping you to achieve it.
Cambium
Profile Blog Joined June 2004
United States16368 Posts
April 24 2009 07:54 GMT
#14
The stack is completely unnecessary -_-;;
When you want something, all the universe conspires in helping you to achieve it.
EsX_Raptor
Profile Blog Joined February 2008
United States2802 Posts
April 24 2009 14:33 GMT
#15
yes exactly, sorry for the ambiguity, i meant using A stack with a LIFO interface.

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.
Please log in or register to reply.
Live Events Refresh
WardiTV Weekly
21:00
WardiTV Mondays #113
WardiTV779
OGKoka 399
BRAT_OK 75
LiquipediaDiscussion
SOOP
19:00
SC2 Kevin Scrim 4v4
ByuN vs RogueLIVE!
IntoTheiNu 212
FanTaSy93
Maru 67
CranKy Ducklings SOOP51
Rex36
ByuN (SOOP) 36
SHIN 34
soO33
herO (SOOP) 19
Rogue 18
Classic 16
LiquipediaDiscussion
[ Submit Event ]
Live Streams
Refresh
StarCraft 2
OGKoka 399
BRAT_OK 75
Maru 67
ByuN (SOOP) 36
Rex 36
SHIN 34
herO (SOOP) 19
Rogue 18
Classic 16
StarCraft: Brood War
Horang2 1937
Jaedong 1139
EffOrt 775
Light 597
BeSt 546
firebathero 497
Mini 455
Rush 381
Stork 214
Larva 207
[ Show more ]
ggaemo 168
Soulkey 150
Killer 126
Mind 106
Hyuk 104
Hyun 96
FanTaSy 93
Barracks 82
Sharp 78
Snow 76
Pusan 65
PianO 59
Leta 59
Movie 50
Shinee 33
soO 33
Terrorterran 32
HiyA 28
JYJ 25
sorry 18
Noble 16
zelot 16
Bishop 15
scan(afreeca) 10
ZergMaN 9
sOs 8
Icarus 7
Dota 2
monkeys_forever325
BananaSlamJamma268
syndereN237
Counter-Strike
byalli498
Other Games
singsing2054
B2W.Neo641
dupreeh612
Lowko366
crisheroes223
hiko169
Mew2King45
[ Show 10 non-featured ]
StarCraft 2
• StrangeGG 42
• AfreecaTV YouTube
• intothetv
• Kozan
• IndyKCrew
• Migwel
StarCraft: Brood War
• BSLYoutube
• STPLYoutube
• ZZZeroYoutube
Other Games
• WagamamaTV137
Upcoming Events
Replay Cast
9h 35m
Monday Night Weeklies
1d 3h
PiGosaur Cup
1d 11h
The PondCast
1d 20h
OSC
2 days
Replay Cast
2 days
GSL
2 days
Patches Events
3 days
OSC
3 days
Replay Cast
3 days
[ Show More ]
KCM Race Survival
3 days
RSL Revival
4 days
BSL
5 days
eOnzErG vs StRyKeR
Cross vs JDConan
RSL Revival
5 days
BSL
6 days
Bonyth vs Doodle
Kyrie vs Jimin
WardiTV Weekly
6 days
Liquipedia Results

Completed

Individual League
Blizzard Classic Cup 2026
HCC Season 3

Ongoing

Acropolis #5
KCM Race Survival 2026 Season 4
International ShieldBattery League
BSL Season 23
IPSL Winter 2026-27
YSL S4
Calamity Cup Div. A Season 8
Underdog Cup 2026 Div 2-3
BLAST Rivals Fall 2026
IEM Beijing 2026
PGL Masters Bucharest 2026
Stake Ranked Episode 5
1win Private Club #2
Thunderpick World Champ. '26
ESL Pro League Season 24
Stake Ranked Episode 4
1win Private Club #1
Logitech G Play Connect 2026
SL StarSeries Fall 2026
FISSURE Playground #3
BLAST Open Fall 2026

Upcoming

Sector 591
SC4ALL II: Brood War
BSL 23: Non-Korean Championship
HSC XXX
Stellar Fest 2: Lunar Cup
StarCraft2 Weekly Open Tournament 2026 Grand Finals
SC4ALL II: StarCraft II
Kung Fu Cup 2026 Grand Finals
RSL Offline Finals
IEM Kraków 2027
PGL Bucharest 2027
BLAST Bounty Winter 2027
PGL Major Singapore 2026
Stake Ranked Episode 6
TLPD

1. ByuN
2. TY
3. Dark
4. Solar
5. Stats
6. Nerchio
7. sOs
8. soO
9. INnoVation
10. Elazer
1. Rain
2. Flash
3. EffOrt
4. Last
5. Bisu
6. Soulkey
7. Mini
8. Sharp
Sidebar Settings...

Advertising | Privacy Policy | Terms Of Use | Contact Us

Original banner artwork: Jim Warren
The contents of this webpage are copyright © 2026 TLnet. All Rights Reserved.