CODEWITHSUNDEEP
pythonrecursion
nxheller
nxheller

Reputation: 125

Understanding basic recursion using Python

I'm having trouble visualizing what actually happens in a recursive function. I've tried drawing activation frames and following the flow of data, but I get lost along the way. The visualizer at PythonTutor.com doesn't help as much as I'd hoped.

Here's a function that determines the number of digits in a number using recursion. 

def digits(x):
    if x > 0:
        return 1 + digits(x // 10)
    else:
        return 0

Why is the 1 the only things that "survives" from one activation frame to another?

Upvotes: 0

Views: 183

Answers (3)

benSooraj
benSooraj

Reputation: 465

So if I am to consider x = 20, the flow would be as follows:

End:   result = 2 <-----------.
                              |      +
Start: digits(20) ==> returns 1 <-----------.
                          +                 |      +  
                      digits(2) ==> returns 1 <-----------.
                                        +                 |
                                    digits(0) ==> returns 0

Upvotes: 2

Yunhe
Yunhe

Reputation: 665

Take digits(10) as an example:

digits(10):
    if 10 > 0:
        return 1 + digits(10 // 10)
    <==>return 1 + digits(1)
    <==>return 1 + 
                    if 1 > 0:
                        return 1 + digits(1 // 10)
                    <==>return 1 + digits(0)
                    <==>return 1 + 
                                    if 0 > 0:
                                        return 1 + digits(0 // 10) 
                                    else:
                                        return 0
                    else:
                        return 0
    else:
        return 0

  • digits(0) returns 0;

  • digits(1 // 10) returns 1 + digits(0) = 1 + 0,

  • digits(10) returns 1 + digits(1 // 10) = 1 + 1 + 0 = 2

Upvotes: 0

Daenyth
Daenyth

Reputation: 37431

With recursion, it's often useful to start with the base case. You can work it out on paper easily enough.

digits(0)
x = 0
if x > 0 # false
return 0
digits(0) == 0

digits(1)
x = 1
if x > 0 # true
return 1 + digits(1 // 10)
return 1 + digits(0) # 1//10==0
return 1 + 0  # digits(0)==0
return 1
digits(1) == 1

...

digits(10)
x = 10
x > 0 # true
return 1 + digits(10 // 10)
return 1 + digits(1)
return 1 + 1
return 2
digits(10) == 2

And so on.

Upvotes: 0

Related Questions