0

I'm working on the following recursive loop example from the Python Essentials 1, and I don't really understand what's happening, hoping someone can shed some light.

def fun(a):
    if a > 30:
        return 3
    else:
        return a + fun(a + 3)

 print(fun(25))

The output is 56. I don't really understand what's happening with the function - it's almost like it's taking a + 3 making 28, and that value is then substituted into a then returned, however I'm not sure if that's what's actually happening and I don't want to 'decide' that's the case if it's not.

Where it gets really interesting is when I started value substitution to try and make sense of it, substituting values in place of the 3. I get the following:

return a + fun (a + 0) = // RecursionError: maximum recursion depth exceeded in comparison
return a + fun(a + 1) = 168
return a + fun(a + 2) = 84
return a + fun(a + 3) = 56
return a + fun(a + 4) = 57
return a + fun(a + 5) = 58
return a + fun(a + 6) = 28
return a + fun(a + 7) = 28

In fact any integer value greater than or equal to 6 seems to give the same answer, so I would assume I was wrong with my initial analysis of what's happening.

I also tried to put a while loop in there to see what was happening as below:

def fun(a):
    i = 1
    if a > 30:
        return 3
    else:
        while i <= 10:
            return a + fun(a + i)
            i += 1
            print(i)
        

print(fun(25))

However this finishes the program with a value displayed of 168, presumably as the value of a is now over 30.

I think I may be making several massively erroneous assumptions here, hoping someone can help :)

user1047228
  • 17
  • 6
  • You can check this out regarding the [RecursionError](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it). It's pretty much safety net for an "infinite" recursion which could cause a `stack overflow` (exceeding memory usage essentially). – Tharu Sep 30 '22 at 12:57

4 Answers4

4

You just have to follow step by step.

The first time you call fun with a=25. This isn't above 30, so you hit the line

return a + fun(a + 3)

which is

return 25 + fun(25 + 3)

so the result is 25 + fun(28). As 28 isn't above 30 it's going to do the same again, effectively turning that first return into

return 25 + (28 + fun(28 + 3))

or

return 25 + (28 + fun(31))

Now, 31 is greater than 30 so this call will return 3 directly, giving a final result of 25 + 28 + 3 which is 56.

Kemp
  • 3,467
  • 1
  • 18
  • 27
  • Thanks - this was so useful. I also understand what's going on in the `while` loop now, it's adding the value of `a + 1` into the `return` value until `a + 1` goes above 30, at which point it adds 3 to it. I think I've got my head round this a bit :) – user1047228 Sep 30 '22 at 13:21
  • 1
    @user1047228 The `while` loop doesn't actually loop, since you immediately return on the first iteration. Neither `i += 1` nor (more obviously) `print(i)` ever execute. – chepner Sep 30 '22 at 13:29
  • That's interesting.... I can see that the `print(i)` never executes in the output, but the value output by the compiler equates to : `25 + 26 + 27 + 28 + 29 + 30 + 3` which is as if the loop is taking place anyway - what's actually happening then if the loop isn't executing? – user1047228 Sep 30 '22 at 13:35
  • 1
    You're calling `fun` with values that increase by 1 each time and adding those onto the result. Your loop isn't doing the work, the recursive calls are doing the work. Your change makes it exactly the same as the original that adds 3, except now it adds 1 instead. – Kemp Sep 30 '22 at 13:40
2

Little breakdown of your code :

if a > 30 : the function terminates and return 3 (i.e. a is in ]30, infinity[. else : this will compute fun(x) with x = a+3 until x reaches 30.

for 25 we will have then :

25 + fun(25+3)
25 + fun(28)
25 + 28 + fun(28+3)
25 + 28 + fun(31)
25 + 28 + 3
53 + 3
56

Python will have a recursion each time it is needed (Hence each call of your fun(a)).

Th3Wh1t3Q
  • 89
  • 4
1

The concept of recursion is to go deeper in the called function every time the condition is not met.

Here we check everytime the function is called if the value passed, here a, met the condition IS a HIGHER THAN 30.

If we execute step by step for fun(25) we got this :

First depth :

IS 25 HIGHER THAN 30 ? => False

Then we return `25 + fun(25 + 3)` or `25 + fun(28)` # We call a second time `fun()`

Second depth :

IS 28 HIGHER THAN 30 ? => False

Then we return `28 + fun(28 + 3)` or `28 + fun(31)` # We call a third time `fun()`

Third depth :

IS 31 HIGHER THAN 30 ? => True

Then we return 3 this time # we don't go deeper because the condition is met. From this point we will return to the top and adding every results have previously.

Once we got to the bottom we have to return to each depth until reaching level 1. If we do this we got this :

result = 25 + (28 + (3))

result = 25 + (31)

result = 56

Aesahaettr
  • 171
  • 4
1

Each function call has its own argument. It's always named a, but the value is different. Using something called equational reasoning (which requires pure functions without side effects to work properly, but fun happens to be pure), we can trace this as follows:

fun(25) == 25 + fun(28)
        == 25 + 28 + fun(31)
        == 25 + 28 + 3
        == 53 + 3
        == 56

In what you were doing, any value k >= 6 makes fun(a + k) immediately return 3. Only the smaller values allow one or more additional recursive calls. (0, of course, leads to infinite recursion, because the argument makes no progress towards the base case.)

No recursive call changes the value of a in the caller; they simply get their own (progressively larger) value of a when called.

chepner
  • 497,756
  • 71
  • 530
  • 681