Recursion expression explanation? (python)

Question

I've been doing some coding exercises and came across this solution which I'd love to understand.

Problem (I re-wrote it a bit so it's not easily searchable):

Write a function that takes in a positive parameter n and returns the number of times one must multiply the digits in n before reaching a single digit. For example:

 f(29) => 2  # Because 2*9 = 18, 1*8 = 8, 
                       # and 8 has only one digit.

 f(777) => 4 # Because 7*7*7 = 343, 3*4*3 = 36,
                       # 3*6 = 18, and finally 1*8 = 8.

 f(5) => 0   # Because 5 is already a one-digit number.

Someone's solution:

from operator import mul
def f(n):
    return 0 if n<=9 else f(reduce(mul, [int(i) for i in str(n)], 1))+1

What I don't understand is how this "+1" at the end of the expression works. Sorry I couldn't title the question more accurately, but I don't know what this is called.

Thanks!

I think it becomes much clearer if you split that ternary up to a proper if-else. What would happen/what would the function return if you remove the +1? The , 1 in the reduce, however, is redundant, as we already know that the list is non-empty. reduce(mul, map(int, str(n))) is enough (and much more elegant IMHO) — tobias_k
– tobias_k, Commented Mar 26, 2018 at 10:01
I've tried removing the +1, it returns 0. I understand that +1 essentially adds 1 to count but I don't understand how it does that if we never defined the count variable... :/ — P. Prunesquallor
– P. Prunesquallor, Commented Mar 26, 2018 at 10:04
It adds +1 for each "depth" of the recursion, hence you end up with the total "depth", i.e. how often you have to multiply the digits. — tobias_k
– tobias_k, Commented Mar 26, 2018 at 10:06

Vinujan.S · Accepted Answer · 2018-03-26 11:21:44Z

5

It is adding 1 to the count and calling function for the multiplied value

Lets take f(777) => 4,

It will add one and call f - 343
count = 1
It will add one and call f - 36
count = 2
It will add one and call f -18
count = 3
It will add one and call f - 8

so the result is 4

functions call will look like

f(7777)
  =1+f(343)
  =1+(1+f(36))
  =1+(1+(1+f(18)))
  =1+(1+(1+(1+f(8))))
  =1+1+1+1+0 = 4

edited Mar 26, 2018 at 11:21

answered Mar 26, 2018 at 9:55

Vinujan.S

1,31916 silver badges28 bronze badges

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

4 Comments

P. Prunesquallor Over a year ago

Thanks for the reply :) I assumed adding count is what it does, but didn't get how it works. We never defined a count variable or anything. Is there a name/term for this sort of thing, so I can google it additionally? :)

Vinujan.S Over a year ago

yeah, good question we never defined count variable, but it will be taken care by function call stack (recursion) . After all recursively called functions returned, final result will be returned from the 1st function call,

Vinujan.S Over a year ago

refer some more recursion examples and try to come up with how computer will execute the recursive function... that will help you get the whole idea... cheers...

tobias_k Over a year ago

It might be clearer if you reverse the terms of the "calling stack" and add some = in between and the 0 in the final row, i.e. f(7777) = f(343) + 1 = ... = (((0 + 1) + 1) + 1) + 1 = 4

Vincent · Accepted Answer · 2018-03-26 10:16:22Z

You can get some insight by first considering the iterative approach:

def f(n):
    for i in count():
        if n <= 9:
            return i
        digits = [int(i) for i in str(n)]
        n = reduce(mul, digits, 1)

and find the corresponding recursion:

def f(n, i=0):
    if n <= 9:
        return i
    digits = [int(i) for i in str(n)]
    next_n = reduce(mul, digits, 1)
    return f(next_n, i+1)

Notice that instead of using the i argument, one can increment the return value:

def f(n):
    if n <= 9:
        return 0
    digits = [int(i) for i in str(n)]
    next_n = reduce(mul, digits, 1)
    return 1 + f(next_n)

It is then possible to move to a fully functional approach removing the affectations:

digits = lambda n: map(int, str(n))
product = lambda xs: reduce(mul, xs, 1)
digit_product = lambda n: product(digits(n))
f = lambda n: 0 if n <= 9 else 1 + f(digit_product(n))

Collectives™ on Stack Overflow

Recursion expression explanation? (python)

2 Answers 2

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related