CODEWITHSUNDEEP
pythonpython-3.xrecursion
MathsIsHard
MathsIsHard

Reputation: 277

Having trouble understanding recursion

I was doing the first recursion exercise on this here: http://cscircles.cemc.uwaterloo.ca/16-recursion/

I followed the obvious hint and made this:

def countup(n):
  if n == 0:
    print('Blastoff!')
  else:
    countup(n - 1)
    print(n)

So the code basically counts up from 0(blastoff) to n. I just don't understand how it works - i looked in the visualiser and it goes through countup(n) to countup(0) at which point it print's off 'Blastoff', all good. After this it sort of...stays in the else loop and starts printing out the previous n values..why would it do this. Does it store the n values for some reason and even if it does how does this codes mechanism work exactly? Any help will be appreciated. Many thanks.

Upvotes: 1

Views: 1135

Answers (3)

dawg
dawg

Reputation: 103744

Consider the variant:

def countup(n):
  if n == 0:
    print('Blastoff!')
  else:
    print(n, end=', ')
    countup(n - 1)
       # print(n, end=', ')    reverse

Prints:

5, 4, 3, 2, 1, Blastoff!

Vs reverse the order of the print with the recursive call:

def countup(n):
  if n == 0:
    print('Blastoff!')
  else:
        # print(n, end=', ')    reverse  
    countup(n - 1)
    print(n, end=', ')

Prints:

Blastoff!
1, 2, 3, 4, 5,

You can now see that with the recursive call of countup(n - 1) before the print(n, end=', '), the function must go all the way to the end test of if n == 0: before any print is encountered.

Once the condition of if n == 0: is met, then the entire call chain is unwound printing the arguments to countup in the reverse order.

Consider as another classic recursive example reversing a string:

def rrev(s):
    if s == "":
        return s
    else:
        return rrev(s[1:]) + s[0]

Or, more succinctly:

def rrev(s):
    return rrev(s[1:]) + s[0] if s else s

Upvotes: 1

Martijn Pieters
Martijn Pieters

Reputation: 1121386

Each time countup() calls itself, it'll eventually return to that same point where it called. The next line will then print n, as it was during that function call.

And each time you call a function, all its names are created anew, they are local. As such, each time you call countup() you have a local, independent value for n.

Essentially you create a chain of countup() calls:

  • countup(2): n is 2, not 0, so the else branch is executed, calls countup(1)

    • countup(1): n is 1, not 0, so the else branch is executed, calls countup(0)

      • countup(0): n is 0, print Blastoff!!, and the function returns


      The countup(0) call returned, next line prints n, still 1 in this call. Next, the function returns.

    The countup(1) call returned, next line prints n, still 2 in this call. Next, the function returns.

Upvotes: 5

Omid Kamangar
Omid Kamangar

Reputation: 5778

It uses recursion to print the numbers.
The best way to understand this is by an example:

countup(3)
  countup(2)
    countup(1)
      countup(0)
        n == 0
        print('Blastoff!')
    print (1)
  print(2)
print(3)

Each time the function is called, it calles the same function with n-1, until n==0. At this point, it begins printing numbers as shown.

Upvotes: 4

Related Questions