-5

I'm relentlessly but fruitlessly trying to comprehend how recursion works. I have an example from one tutorial ('Problem solving with algorithms and data structures'). Why is it, that after the recursion has happened, it again makes 5 "additional" steps with the value of the variable rising upward?

Code: 

def tree(branchLen):
    if branchLen >= 5:
        print(branchLen, '#it is pretty understandable')
        tree(branchLen-15)
        print(branchLen, '#stop! Why rising (get backward)?')

tree(75)

Output: 

75 #it is pretty understandable
60 #it is pretty understandable
45 #it is pretty understandable
30 #it is pretty understandable
15 #it is pretty understandable
15 #stop! Why rising (get backward)?
30 #stop! Why rising (get backward)?
45 #stop! Why rising (get backward)?
60 #stop! Why rising (get backward)?
75 #stop! Why rising (get backward)?

The question has been edited several times to provide more readability (according to remarks). There may be a bit of discrepancies between questions and answers.

Håken Lid
  • 22,318
  • 9
  • 52
  • 67
Никита Давыдов
  • 63
  • 3
  • recursion just means the function calls itself a number of times, you can have conditions and parameters in the mix – ragardner Jun 29 '17 at 09:31
  • This is basic recursion problem. Python has to process through all the lines of the function. So once it called `tree()` inside of `tree()` and it finish the second `tree()` it has to come back to the first one and finish to process to the end of the function. (PS: Your algo does that 5 times because there is 5 call of `tree()`) – Nuageux Jun 29 '17 at 09:33
  • You perform a recursion as long as `branchLen>1`. That means the last "pretty understandable" line calls `tree(0, t)`. At that point you stop the recursion and start to return, and you start to see the second output. Note that in the previous recursions you didn't change `branchLen`, so you see the previous values again. – mwil.me Jun 29 '17 at 09:38
  • 3
    If you're stuck on recursion you may simply be stuck on the fact that a function calls itself. Don't think that's something special. Think of it as a call to *some other function*. Presumably you'd understand if `a()` called `b()` which called `c()`? It's no different here, `tree()` calls `tree()` which calls `tree()`; the fact that that's the same function three times is pretty irrelevant. Knowing this, it should be pretty simple to follow the execution path. – deceze Jun 29 '17 at 09:38
  • Possible duplicate of [Understanding Recursion](https://stackoverflow.com/questions/717725/understanding-recursion) – Prune Jun 29 '17 at 15:30

1 Answers1

0

You need to understand the scope rules in python and concept of recursion. The flow of calling of functions is as follows:

tree(75, t) --> tree(60, t) --> tree(45, t) --> tree(30, t) --> tree(15, t) --> tree(0, t)

; and then the if condition fails and the scope returns to the function from whom the function was called, that is the "parent function".
So, after the execution of tree(branchLen-15,t) in the scope of tree(15, t), the recursive call simply returns and the print(branchLen, '#stop! Why rising (get backward)?') line gets executed in the scope of tree(15, t), then this function ends and the scope returns to the parent function (which called tree(15, t)), viz. tree(30, t) and the cycle goes on till the tree(75, t) which made the first recursive call completes.
Best way to understand recursion is through stacks, see here for a good explanation.

Shraddheya Shendre
  • 171
  • 4
  • 14