Python: Recursion

Question

def counter(n):
  if n < 0:
      return
  else:
      print '1st print', n
      counter(n-1)
      print '2nd print', n

print counter(3)

# 1st print 3
# 1st print 2
# 1st print 1
# 1st print 0
# 2nd print 0
# 2nd print 1
# 2nd print 2
# 2nd print 3
# None

So after fiddling around with the recursion functions a bit I realized something quite peculiar and I can't quite wrap my head around it. I understand the first part of the function where it prints from 3 to 0, but I don't understand the second part when it prints from 0 to 3 again. Wouldn't the function just stop when n = 0?

Note that you print n twice - once before the recursion and once after it. Once all of the recursive calls are done, all the methods that are waiting on their recursive calls print n again (in the opposite order). Try running it yourself with a pen and paper. — Ant P
– Ant P, Commented Jun 5, 2014 at 10:31
This is python. Please try to intend your code or it can ruin everything. I just edited it. — Abdul Fatir
– Abdul Fatir, Commented Jun 5, 2014 at 10:33
@AbdulFatir Thank you for the indentation fix, but Commonwealth English ("realised") is perfectly acceptable and should not be edited. — chrylis -cautiouslyoptimistic-
– chrylis -cautiouslyoptimistic-, Commented Jun 5, 2014 at 10:34
I know that. I just edited it for the 6 character edit thing. :| — Abdul Fatir
– Abdul Fatir, Commented Jun 5, 2014 at 10:35

Martijn Pieters · Accepted Answer · 2014-06-05 10:40:47Z

8

Your recursive call still returns to the parent function that invoked it. In that scope n has not changed.

Function locals are still local to the current frame even if you keep calling the function from itself.

Your recursion call looks like this:

counter(3):
  n = 3
  |
  | counter(n - 1)
  |   n = 2
  |   |
  |   | counter(n - 1)
  |   |   n = 1
  |   |   |
  |   |   | counter(n - 1)
  |   |   |   n = 0
  |   |   |   |
  |   |   |   return
  |   |   |
  |   |   n is still 1 here
  |   |   return
  |   |
  |   n is still 2 here
  |   return
  |
  n is still 3 here
  return

edited Jun 5, 2014 at 10:40

answered Jun 5, 2014 at 10:34

Martijn Pieters

1.1m326 gold badges4.2k silver badges3.4k bronze badges

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

2 Comments

Tim Over a year ago

Nice, also congratulations on reaching 250k :-) (well, nearly)

Martijn Pieters Over a year ago

@TimCastelijns: tomorrow, I'm sure. And then onwards. :-P Thanks!

Danstahr · Accepted Answer · 2014-06-05 10:39:26Z

Yes, the function would stop - on the last level. But the higher levels will still process the second output.

Let me give you an example. You live on Nth floor of a building and you want to go to the ground level and back up. Since your building doesn't have an elevator, you decide to follow the algorithm :

def godown(n):
    if n <= 0: # already there
        print "At the ground level"
        return
    print "Going down"
    godown(n-1) # we moved one floor lower
    print "Going back up"

Once you're at the ground floor, you suddenly won't forget that you wanted to go back up. You know it and even if you're at the ground floor (which is the terminating condition), you go back up. It's the same for the computer - it doesn't terminate all the functions together, but just the one and finishes the executing of all the commands from the previous calls. It works just as any other function call :

def bar():
    print "inBar"
    return

def foo():
    print "preBar"
    bar()
    print "postBar"

astralwolf · Accepted Answer · 2015-12-22 08:38:47Z

I simplified your code a little, but in essence it is the same. My answer is similar to the first guy's answer, but I did not understand his answer. I changed it to this.

def counter(n):
    if n == 0:
        return
    else:
        print ("Hi")
        counter(n-1)

        print("Hi again!")

counter(3)

Recursion means calling a function that is already executing. So when you do counter(n-1) you are creating another counter function. There are 2 counters currently being run. The original one is halted until the second one is finished and so on.

def counter(n): #N is 3 here!
    if n == 0:
        return
    else:
        print ("Hi")
        counter(n-1) ---------> (NEW FUNCTION)  def counter(2):
                                                    print("Hi")
                                                    counter (n-1) ---------> (NEW FUNCTION)def counter(1):
                                                                                                print("Hi")
                                                                                                counter(n - 1) ---------> NEW FUNCTION def counter(0)
                                                                                                                                            #function returns and ends
                                                                                                                                             |
                                                                                                (program still running)                      |  
                                                                                                                                             |
                                                                                                print ("Hi again")              <-------------
                                                                                                        |
                                                (program still running)            <--------------------|            

                                                print("Hi again")
                                                       |
 (program still running)                  <------------|

  print("Hi again!")

Collectives™ on Stack Overflow

Python: Recursion

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related