1

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)
Improve this question
9
  • 1
    The way I conceptualize things like this is by executing the program by hand on paper, writing down the values of the variables. 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 Commented Feb 16, 2014 at 4:12
  • Yes exactly! I tried doing that. May be I am missing something. Please shed some light. Commented Feb 16, 2014 at 4:12
  • Hint print range(step, 4) before the for loop. Commented Feb 16, 2014 at 4:14
  • 1
    Hard-coded iterative version: ideone.com/cILsb1 Commented Feb 16, 2014 at 4:42

3 Answers 3

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

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)
Improve this answer

6 Comments

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.
PEP 8: Avoid extraneous whitespace in the following situations: ... Immediately before the open parenthesis that starts the argument list of a function call ...
@falsetru is correct, see 3rd item: python.org/dev/peps/pep-0008/#pet-peeves
@falsetru I think it is hilarious that this section of the PEP is titled "Pet Peeves". Exactely to the grain.
@Hyperboreus, It seems like you mentioned wrong guy ;
|
-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

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.