python - Understanding how stack frames work in recursive function -


python/cs newbie here, trying understand how particular recursive function works "under hood" in terms of how function's stack frames operating , values they're "holding."

i know lot has been written/posted recursive functions on here, , there illustrative examples of how work, concepts of recursion , how stacks work/what in recursive function little tricky , i'm not finding clear , concise explanations.

let's have following recursive function reverses characters in string:

text = "hello" def reverse_string(text):         if len(text) <= 1:             return text         return reverse_string(text[1:]) + text[0] 

which outputs: olleh

i'm thinking frames reverse_string(text[1:]) work follows:

global frame text    "hello" reverse_string    reverse_string text    "hello"  reverse_string text    "ello"  reverse_string text    "llo"  reverse_string text    "lo"  reverse_string text    "o"  return value   "o" 

but happens after value "o" returned , terminating base condition met? how text[0] work in function arrive @ "olleh" ?

just taking example walk.

once reach terminating condition, remaining frames pop'd in reverse order.

suppose reach terminating condition in case return text "hit" , text = "o" returned. in previous frame have reverse_string(text[1:]) + text[0] reverse_string("o") + "l" = "o" + "l" = "ol" = reverse_string(text[1:]), reverse_string(text[1:]) call previous frame (the 1 text equal "llo"). continuing logic, reverse_string("lo") + "l" = "ol" + "l" = "oll".

we continue same idea until reach "top" frame return "olleh".


Comments