Recursion accumulation or how to count number of recursion calls in Python?

Question

I've read a lot of the Python manual, but can't figure this one out.

Two local variables in a function that calls itself, and only one of them is behaving "static" like.

Here's the code snippet:

def sort_bubble(local_itera, difficulty):   
    #local_itera = itera[:]
    sorted_count = 0
    nrecursions = 0

    for i in range(difficulty - 1):
        val1 = local_itera[i]
        val2 = local_itera[i+1]

        if local_itera[i] == min(val1, val2):
            sorted_count += 1
            continue # skip sorted pairs
        else: # swap
            local_itera[i] = min(val1, val2)
            local_itera[i+1] = max(val1, val2)

    if not sorted_count == difficulty - 1: # recurse if not sorted
        nrecursions += 1
        sort_bubble(local_itera, difficulty)

While sorted_count gets incremented, nrecursions does not, which I would like to use to count the number of recursion calls.

Please notice that the purpose of this is to be used as a self-contained function (this is just prototyping):

global variables defeat the purpose
class syntax overhead defeats the purpose

Addendum

I am thinking in the following direction.

(taken from Python manual)

def whats_on_the_telly(penguin=None):
    if penguin is None:
        penguin = []
    penguin.append("property of the zoo")
    return penguin

But this is also overkill.

Fix the indentation in your code and explain where exactly is the problem and which variable are you referring to — Sheldore, Dec 23 '18 at 14:33
@Bazingaa what's wrong with indentation? AAAH, I got it. Sorry. — Ate Somebits, Dec 23 '18 at 14:34
`nrecursions` does not get incremented because you are not incrementing it anywhere in your code unlike `sorted_count ` — Sheldore, Dec 23 '18 at 14:35
The code snippet belonging to the function should be indented. Currently the function has no body — Sheldore, Dec 23 '18 at 14:35
`nrecursions` should be initialised ONLY ONCE outside the recursive function and simply incremented inside the recursive function. By the way NO variable behaves as static, both `sorted_count` and `nrecursions` are being initialised all the time inside function body and acquire some values which are NOT kept from call to call — Nikos M., Dec 23 '18 at 14:43
@NikosM. I get you. But `sorted_count` actually stops the recursion, how come? — Ate Somebits, Dec 23 '18 at 14:44
because it acquires some value (during a single recursion call) that stops the recursion based on the `if ..` test. There is no magic it is simple. In any case it DOES NOT keep its value from cal, to call as it is being re-initialised every time the function is called. This is clear — Nikos M., Dec 23 '18 at 14:46
@ChristianDean Question (title) edited for distinguishing purposes. — Ate Somebits, Dec 23 '18 at 14:58
@NikosM. Hm... most of the time, dare not say 100% of the time, the `sorted_count` nails it, so *"acquires some value"* sounds a little vague to me. The only time this code fails is if the algorithm accidentally exceeds the `sys.getrecursionlimit()` value, which can happen since item count is set to1002. Or perhaps not...? — Ate Somebits, Dec 23 '18 at 15:02
There are other options on the duplicate I linked to @AgnesK.Cathex. You could, for example, simply make a class that is a callable object. That's self-contained, yet provides you with local static variables. — Christian Dean, Dec 23 '18 at 15:07
@ChristianDean yeah, class variables are "static", although classes in Python (2.7 at least) do not implement real encapsulation, and I believe there are other "methods". I'm thinking of `yield` - could it be used in this case? — Ate Somebits, Dec 23 '18 at 15:12
@ChristianDean *"callable object"*, as in, no need to instantiate it? — Ate Somebits, Dec 23 '18 at 15:40
Nah, @AgnesK.Cathex. Callable as in being able to use the class instance as a function. You might be able to get `yield` to work for you though. — Christian Dean, Dec 23 '18 at 15:43
@ChristianDean right, somewhat like JavaScript where most objects can be called as a function? Is there less overhead then, compared to method calls? — Ate Somebits, Dec 23 '18 at 15:47
@NikosM. Hey, you pointed me in somewhat right direction. Here's what I came up with: after recursion, function returns `difficulty - sorted_count` where `difficulty` is actually the number of items (bad coding style there). Thus, I get number of recursion calls, which tends to hover around the number of items. *Is this normal for bubble sort?* Or is the formula faulty? — Ate Somebits, Dec 23 '18 at 15:52
I would say both. Your `difficulty - sorted_count` formula just measures the number of swaps made in the first pass, not the number of (recursive) passes needed to sort the array. But, coincidentally, the number of passes needed to sort an array using bubble sort typically _is_ quite close to the number of elements in the array, especially if the input array happens to contain a "[turtle](https://en.wikipedia.org/wiki/Bubble_sort#Rabbits_and_turtles)" (i.e. a low-ranking element near the end of the array). — Ilmari Karonen, Dec 23 '18 at 18:47
Anyway, I'm not sure if your question is still a duplicate or not after your latest edits, but that probably means that it _is_ too unclear for SO in its current form. If you'd like to have it reopened, consider editing it to focus _only_ on your actual problem (i.e. how to count the number of recursive calls) and removing all the distracting stuff about "static" variables. — Ilmari Karonen, Dec 23 '18 at 18:56
**Moderator Note**: Please do not update your post to change the question completely in order to invalidate the current answers. You can ask a new question by creating a separate post. — Bhargav Rao, Dec 24 '18 at 08:03

score 1 · Accepted Answer · edited Dec 23 '18 at 16:09

1

The problem seems to be that unlike sorted_count, you are not incrementing the number of calls to your function anywhere. To count the number of recursions, you need to properly increment it. [OPs note: QUESTION UPDATED]

Moreover, your nrecursions will be reinitialized to 0 during each function call because you have placed it inside the function. So you should initialize it to 0 outside the function.

In my opinion, this the correct place to increment it as follows. In addition, you need to make your variable of type global

nrecursions = 0

def sort_bubble(local_itera, difficulty):   
    global nrecursions
    # Function body

    if not sorted_count == difficulty - 1: # recurse if not sorted
        nrecursions += 1 # <--- added here
        sort_bubble(local_itera, difficulty)

edited Dec 23 '18 at 16:09

Ate Somebits

287
1
18

answered Dec 23 '18 at 14:38

Sheldore

37,862
7
57
71

The question address the fact that `sorted_count` is also initialized in the body. – Ate Somebits Dec 23 '18 at 14:42
@AgnesK.Cathex: You should not initialise the recursion variable inside the function. Think about it, as soon as you call it again, the variable is set to zero so you will never get any increment – Sheldore Dec 23 '18 at 14:44
@ChristianDean: I think as long as you are using the update value of `nrecursions` within the function, it is ok. Only if you use if after exiting the function, you need to define it global or else it will always be 0 outside the function. Right? – Sheldore Dec 23 '18 at 14:50
@ChristianDean: Done – Sheldore Dec 23 '18 at 14:53
@ChristianDean: Done – Sheldore Dec 23 '18 at 14:54
About global variables, Python manual states: *"The global statement is a declaration which holds for the entire current code block. It means that the listed identifiers are to be interpreted as globals. It would be impossible to assign to a global variable without global, although free variables may refer to globals without being declared global."* – Ate Somebits Dec 23 '18 at 15:08
sorry, I'm amending my question as we speak. And you are Flash Gordon of stackoverflow :D – Ate Somebits Dec 23 '18 at 15:16

Recursion accumulation or how to count number of recursion calls in Python?

Addendum

1 Answers1