Understanding basic recursion using Python

Question

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?

Add a couple print statements and print the values prior to the return statement. The hardest part about recursion is remembering that it unwinds itself. Try looking at a few of these examples to see if one clicks for you: cs.cmu.edu/~adamchik/15-121/lectures/Recursions/recursions.html -- I think recognizing a recursive problem is 1/2 the battle in understanding recursion — pyInTheSky
– pyInTheSky, Commented Mar 16, 2016 at 1:51
Also you can learn what is tail recursion which is optimised in most of the modern languages but apparently python did not do that — yue you
– yue you, Commented Feb 5, 2018 at 11:36

benSooraj · Accepted Answer · 2016-03-16 02:34:50Z

2

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

answered Mar 16, 2016 at 2:34

benSooraj

4655 silver badges18 bronze badges

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

Comments

Daenyth · Accepted Answer · 2016-03-16 01:51:56Z

0

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.

answered Mar 16, 2016 at 1:51

Daenyth

37.8k15 gold badges92 silver badges130 bronze badges

Comments

Yunhe · Accepted Answer · 2016-03-16 02:04:10Z

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

Collectives™ on Stack Overflow

Understanding basic recursion using Python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related