CODEWITHSUNDEEP
pythonrecursion
user2526486
user2526486

Reputation: 21

How to understand this nested recursion?

This code has me lost. When run, it outputs sequences which I finds strange:

def print_n(number):
    if (number <= 0):
         return None
    else:
         print number
         print_n(number-1)
    print_n(number-1)

print_n(4)

I thought it would output this sequence:

4,3,2,1,1,2,1,3,2,1

however it actually outputs:

4,3,2,1,1,2,1,1,3,2,1,1,2,1,1

I tried to draw the stack diagram of this function but when I get lost at the second appearance of the print_n(number-1).

I can understand this program without the second appearance of the print_n(number-1), as it's just normal recursion. However, the second print_n(number-1), seems much more complicated than I expected, I don't know how to trace this function call and explain the result...

Upvotes: 1

Views: 2218

Answers (2)

OBu
OBu

Reputation: 5177

I liked the answer of Kevin, but let me add a few words towards "understanding recursion":

I often suggest using sheets of paper representing the stack. each sheet contains its local varaibles and current state - and you can mark the line you are "processing" with a pen.

Use a separate sheet as output / console.

This gives you a very good understanding of what is going on.

Of course, following your code in a debugger and examining the stack trace can be helpful as well. But try the paper-approach first!

Upvotes: 1

Kevin
Kevin

Reputation: 76194

Since the if block has an unconditional return, you can remove the else and the program will continue to behave the same way.

def print_n(number):
    if (number <= 0):
        return None
    print number
    print_n(number-1)
    print_n(number-1)

Here, it's more apparent what is going on: You print number, and then call print_n twice using number-1. You can work backwards to derive the output.

  • print_n(1) prints "1"
  • print_n(2) prints "2" plus "1" plus "1": "211"
  • print_n(3) prints "3" plus "211" plus "211": "3211211"
  • print_n(4) prints "4" plus "3211211" plus "3211211": "432112113211211"

Upvotes: 7

Related Questions