Don't Understand Recursive Function

[muzikman]

Greetings,

I have a recursive function that I ran through the debugger in PyCharm and I am having a difficult time making sense of some of it. Here is the function in question:

def rec_count(number):
    print(number)
    # Base case
    if number == 0:
        return 0
    rec_count(number - 1)  
    print(number)  #After recursion meets base case it then moves on to this print statement. 
                   #When I step into this print statement, it is printing out the numbers in reverse.
                   #What I don't understand is, how can a print statement loop through this number variable?
rec_count(5)

Read the comments to understand my problem. The function prints out the following.

Output:
5
4
3
2
1
0
1
2
3
4
5

When it hits the last print statement, how is it looping through the number variable? It is not a loop but it is acting like one.
Can someone help me understand why this is happening?

Thank You,
Matt

[stranac]

This is the basic structure of your function:

Output:
rec_count(5)
  print 5
  rec_count(4)
  print 5

If we expand all calls like that, we get:

Output:
rec_count(5)
  print 5
  rec_count(4)
    print 4
    rec_count(3)
      print 3
      rec_count(2)
        print 2
        rec_count(1)
          print 1
          rec_count(0)
            print 0
            return 0
            print 0 -- not called because the return ends this call
          print 1
        print 2
      print 3
    print 4
  print 5

Hope that helps.

[bowlofred]

The print statement only prints one number. What is happening is that when you reach the base case, you have 6 instances of rec_count() running. Five are waiting for their call to rec_count() to complete. As each one completes, it moves on with the rest of the program.

As each function finishes, it prints the number. Because of how you have it written, they finish in reverse order, so the numbers are printed in reverse order.

It's not a traditional loop, but recursion is certainly a form of looping. (With different abilities and limitations)

[deanhystad]

Your recursive function is doing this:

def rec_count0():
    return 0

def rec_count1():
    print(1)
    rec_count0()  
    print(1)

def rec_count2():
    print(2)
    rec_count1()  
    print(2)

def rec_count3():
    print(3)
    rec_count2()  
    print(3)

def rec_count4():
    print(4)
    rec_count3()  
    print(4)

def rec_count5():
    print(5)
    rec_count4()  
    print(5)

rec_count5()

If you put a break on "return 0" in rec_count0() the call stack would look something like this:
rec_count5
rec_count4
rec_count3
rec_count2
rec_count1
rec_count0

These are all partially completed functions waiting for a function they called to complete. If you set a breakpoint on "return 0" in your rec_count() function your call stack would look similar.
rec_count
rec_count
rec_count
rec_count
rec_count
rec_count

Again these are all partially completed functions that are waiting for a function they called to complete.

[muzikman]

I am going to have to study your examples. I also have another function I need to post that is driving me nuts. I am new to Python and recursion is a new concept to me because I have never used it. Python can also be used as a procedural language, this is probably why recursion works well. However, I am coming from an OOP background and some of the syntax in Python seems a little counterintuitive. I like strictly type languages because you always know what you're dealing with.

Thank you for your help. I sort of understand it now based on both explanations. Basically, each call is a separate instance, which waits until the child calls are finished for each iteration? Then, base case is met and the child functions return and print out their value, which ultimately closes each call before that, ending with the first call? All functions are still running until the traverse in reverse because the parent is waiting for the child to finish; and finally finish with

rec_count(5):

which is the last to be printed.

Oh. Almost forgot. Is the call stack in the debugger the best way to understand the logic behind recursion? I am using PyCharm.

Thank you so much.

[muzikman]

Your visualization really helped me a lot; especially with the nested calls. Thank you.

This is the basic structure of your function:

Output:
rec_count(5)
  print 5
  rec_count(4)
  print 5

If we expand all calls like that, we get:

Output:
rec_count(5)
  print 5
  rec_count(4)
    print 4
    rec_count(3)
      print 3
      rec_count(2)
        print 2
        rec_count(1)
          print 1
          rec_count(0)
            print 0
            return 0
            print 0 -- not called because the return ends this call
          print 1
        print 2
      print 3
    print 4
  print 5

Hope that helps.

[muzikman]

I will let you know when I post the other function. Your help will be greatly appreciated. I cannot move forward learning Python until I have completely understood recursion. Especially, the tricky ones where you add two calls of the function together such as

return func(n) + func(n - 1)

etc...

[deanhystad]

I avoid recursion whenever possible. It is slow and there is a limit on how many levels deep you can go. You can be a very accomplished programmer and never use recursion.

[muzikman]

I avoid recursion whenever possible. It is slow and there is a limit on how many levels deep you can go. You can be a very accomplished programmer and never use recursion.

I know. I have never used it during my entire career. Only in school when I was learning Pascal.

[muzikman]

Could you possibly take a look at the following post and let me know if I am visualizing and explaining this the correct way?

Thanks in advance.
Matt