Python recursive call inside a loop. How does it work?

Question

I came across a loop with a recursive function call inside, where the start range of loop is incremented as follows. The code outputs the following sequence as below. However, I unable to conceptualize why this particular sequence is generated. Can somebody throw some insight into its working. And how feasible is it to convert this recursive function into an iterative function outputting the same sequence. Please help.

Code:

def foo(step=0):
    for i in range(step, 4):
        print step
        foo(step+1)

foo()

Output:

0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3

Code of similar design to find Anagrams:

def find_anagrams(word, step=0):
    print 'step->', step
    if step == len(word):
        print "".join(word)
    for i in range(step, len(word)):
        print step, i
        word_ = list(word)
        word_[step], word_[i] = word_[i], word_[step]
        find_anagrams(word_, step+1)

The way I conceptualize things like this is by executing the program by hand on paper, writing down the values of the variables. — Barmar
– Barmar, Commented Feb 16, 2014 at 4:11
Indenting output by call depth will make it little bit easier to understand. For example: ideone.com/g0ludx — falsetru
– falsetru, Commented Feb 16, 2014 at 4:12
Yes exactly! I tried doing that. May be I am missing something. Please shed some light. — Shankar
– Shankar, Commented Feb 16, 2014 at 4:12

James Sapam · Accepted Answer · 2014-02-16 07:06:18Z

Let me try:

From your snippet, in every function call i.e foo(step+1) a structure known as an activation record or frame is created to store information about the progress of that invocation of the function. So, When the execution of a function leads to a nested function call, the execution of the former call is suspended and its activation record stores the place in the source code at which the flow of control should continue upon return of the nested call.

Here is the main part:

When step == 4, which in turns range(4,4) == empty list, that time iteration won't happen so it will return None. Then it will move to the previous frame, where it was stopped and start a new iteration and recursive function call until range(4,4).

NB: Recursive base case is only when step == 4, that time range(4,4) and return None.

Every recusion needs a base case other wise it will goto infinite loop.

So, lets see the recursive trace: I am adding i to differentiate the step and iterative increment.

# 1 def foo(step=0):
# 2    for i in range(step, 4):
# 3        print 'i: %d, step: %d' % (i,step)
# 4        foo(step+1)
# 5 foo()

line 5
line 1  foo with step=0  which is default
line 2  range(0,4)                       Frame: A,   0 is over, next=1
line 3  step = 0            Output: i: 0, step: 0
line 4  calling foo(0 + 1)
line 1  foo with step=1
line 2  range(1,4)                       Frame: B,   1 is over, next=2
line 3  step = 1            Output: i: 1, step: 1
line 4  calling foo(1 + 1)
line 1  foo with step=2
line 2  range(2,4)                       Frame: C,   2 is over, next=3
line 3  step = 2            Output: i: 2, step: 2
line 4  calling foo(2 + 1)
line 1  foo with step=3
line 2  range(3,4)                       Frame: D,   3 is over, next=4
line 3  step = 3,           Output: i: 3, step: 3
line 4  calling foo(3 + 1)
line 1  foo with step=4
line 2  range(4,4)                       Frame: E,
         This is an empty list, so it won't come inside the loop, so return None.
         Come back to previous Frame: D, i=3 was used, now increment to 4. So, again range(4,4)
line 2  range(4,4)          Empty list, from Frame: D, return None
         Come back to previous Frame C, now i=3, step was called with value 2
line 2  range(2,4)
line 3  step = 2            Output: i: 3, step: 2, why step == 2 because the function foo was called with step=2
line 4  calling foo(2 + 1)
line 1  foo with step=3
line 2  range(3,4)
line 3  step = 3,           Output : i: 3, step: 3
line 4  calling foo(3 + 1)
line 1  foo with step=4
line 2  range(4,4)          Empty list again, not going inside the list, return None
line 2  range(2,4)          From Frame: B, step was == 1, because the function foo was called with step=1
line 3  step: 1             Output: i: 2, step: 1,  here i ==2, because this is the second iteration of Frame B.
line 4  calling foo(1 + 1)
line 1  foo with step=2
line 2  range(2,4)
line 3  step: 2            Output: i: 2, step: 2

After this it follows the same recursive fashion, until the iterative range is exhuausted i.e range(4,4)

Please let me know if that helps.

falsetru · Accepted Answer · 2014-02-16 09:38:11Z

0

I think your anagram code could be refactored avoiding the recursive loop, by using the stdlib:

from itertools import permutations

def anagrams (word):
    anagrams = set ()
    for p in permutations (word):
        anagram = ''.join (p)
        anagrams |= {anagram}
    return anagrams

def isAnagram (word1, word2):
    return sorted (word1) == sorted (word2)

edited Feb 16, 2014 at 9:38

falsetru

371k69 gold badges769 silver badges659 bronze badges

answered Feb 16, 2014 at 4:55

Hyperboreus

32.5k9 gold badges50 silver badges88 bronze badges

6 Comments

Shankar Over a year ago

Yes! I understand that. But my question is how does the recursive call inside a loop generate such a sequence. I need some insight into the function call.

falsetru Over a year ago

PEP 8: Avoid extraneous whitespace in the following situations: ... Immediately before the open parenthesis that starts the argument list of a function call ...

Nir Alfasi Over a year ago

@falsetru is correct, see 3rd item: python.org/dev/peps/pep-0008/#pet-peeves

Hyperboreus Over a year ago

@falsetru I think it is hilarious that this section of the PEP is titled "Pet Peeves". Exactely to the grain.

falsetru Over a year ago

@Hyperboreus, It seems like you mentioned wrong guy ;

|

Dan Oberlam · Accepted Answer · 2014-02-16 05:20:58Z

-1

Consider the for loop. You are iterating through range(step, 4). If step = 0 then you are iterating over [0,1,2,3], if step = 1 then you are iterating over [1,2,3] and so on. Each time foo(step) is called it iterates over that range - but the range being iterated over in the current call doesn't change. So for the first loop you get an iteration from 0 to 3, the second loop is 1-3, etc.

Why does it print like that? Observe.

for i in range(0,4):
    print 0
    for j in range(1,4):
        print 1
        for k in range(2,4):
            print 2
            for h in range(3,4):
                 print 3

This will have the same output as your recursive function

answered Feb 16, 2014 at 5:20

Dan Oberlam

2,4969 gold badges39 silver badges58 bronze badges

Collectives™ on Stack Overflow

Python recursive call inside a loop. How does it work?

3 Answers 3

Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related