def tri_recursion(k):
if(k>0):
result = k+tri_recursion(k-1)
print(result)
else:
result = 0
return result
print("\n\nRecursion Example Results")
tri_recursion()
Why in this code, when we set a value to tri_recursion, the function add all numbers until 0?
I don’t understand why this result = k+tri_recursion(k-1) makes what I said in the question above.
I don’t know python, but…
First of all, this does nothing unless you pass it something. I changed the last line to:
tri_recursion(4)
Recursion is tricky business. It makes no sense … until you get it. And even then it takes a while to fully sink it.
Whenever I am confused, I start logging out data to see what happens. So, I add a log statement to your code:
def tri_recursion(k):
print("calling tri_recursion with", k)
if(k>0):
result = k+tri_recursion(k-1)
print("result = ", result)
else:
result = 0
return result
print("\n\nRecursion Example Results")
tri_recursion(4)
Now I can see what is happening.
Recursion Example Results
calling tri_recursion with 4
calling tri_recursion with 3
calling tri_recursion with 2
calling tri_recursion with 1
calling tri_recursion with 0
result = 1
result = 3
result = 6
result = 10
On the result =... line, it never fully evaluates before another all is made. In other words, it never makes it to the next line before calling the function again. It keeps calling that function, keeping track of those calls and values in the call stack, until we finally call it with 0. Then we return that value back. As that value gets sent back to the previous call, that result =... line can finish and then the next line gets evaluated. This happens over and over as the call stack “unwinds” and renders its values.
Recursion is a difficult topic and not one that can be explained here. Just stick with it. There might be a good youtube video that will help you explain. Like I said, it’s kind of a weird concept until it “clicks”. Don’t get frustrated.
The sentence you highlighted is indeed recursive in nature because it calls the same function with potentially different values until a condition makes the recursion break and backtrack (unless using tail-call optimization which is a topic for later).
How can you visualize it to better understand it: by unfolding the invocations as a nested call/replace statement that then gets recursively evaluated from left to right.
given k = 3 and
renaming "result" to "r" and
renaming "tri_recursion" to "sum"
===============================================================
recursive statement:
result = k + tri_recursion(k - 1) when k > 0
result = 0 when k <= 0
===============================================================
eval visualization:
sum(r = 3 + sum(given k = 3 - 1 => 2:
r = 2 + sum(given k = 2 - 1 => 1:
r = 1 + sum(given k = 1 - 1 => 0:
r = 0 <- stop condition
return 0)
--------------------------> recursion ended, begin backtracking
r = 1 + 0
return 1)
r = 2 + 1
return 3)
r = 3 + 3
return 6)
-> 6 yielded
Another less cluttered way of visualizing it:
|> first stackframe
| |> second stackframe
| | |> third stackframe
| | | |> last stackframe & stop condition
(3 + (2 + (1 + (0))))
(3 + (2 + (1 + 0)))
(3 + (2 + (1)))
(3 + (2 + 1))
(3 + (3))
(3 + 3)
(6)
6 <- result
As you can see these function executions are stackframes that can be thought as “nested” one inside the other like a matryoshka doll. But in reality, deep down to the bare metal, it’s a stack data structure when it comes to functions in JavaScript. You can also represent these things as a tree graph but I’m too lazy to draw one rn.
Thanks, I think I understand.