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
Post a Comment