Python – How to Write a Suitable Recurrence Relation for a Function

python

I have an exercise in which I am require to build a recursive function that takes a natural number and returns "True" if it is divisible by 3, or "False" otherwise, using the 3-divisibility rule. Then I was asked to write a recurrence relation of this function. The function I wrote is:

def divide3(n):
    i=0
    while i in range(0,len(str(n))-1):
        if (sum(n, i))%3==0:
            if (divide3(int(str(n)[i+1:])))==True:
                return True
            else:
                return False
        continue

What I don't understand is how I am supposed to write an n-depended recurrence relation, if the number of operations I make is related to the number of digits in n, and has nothing to do with n itself. I would appreciate any help in the subject.

Best Answer

Sorry, but your code doesn't work at all and makes no sense whatsoever. If it gets into the loop at all, it immediately gets killed by an error. Did you even try it? I'd recommend first getting it right instead of trying to come up with a recurrence relation for something broken. Or did they ask you for the recurrence relation because they saw your code and also had no idea what you were doing, so this is their way of trying to get you to explain?

What's "the 3-divisibility rule"? You mean that a number is divisible by 3 if and only if its digit sum is? If so, then that directly tells you what to do: When asked whether some number is divisible by 3 and you don't know right away, ask yourself whether its digit sum is divisible by 3. If that number is still too large to see it directly, ask yourself whether the digit sum of that number is divisible by 3. And so on.

Straight-forward implementation then:

def divide3(n): return n in (0, 3, 6, 9) if n < 10 else divide3(sum(map(int, str(n))))

Bit more interesting:

def divide3(n): return n in (0, 3, 6, 9) if n < 10 else divide3(n//10 + n%10)

(Sorry about the formatting, don't know how to spoilerize code.)

Related Solutions

Python Design – Best Practices for Python Factory Functions

The choice should between a factory function and a third option instead; the class method:

class Foo(object):
   def __init__(self, data):
      ...

   @classmethod
   def fromSourceData(klass, sourceData):
      return klass(processData(sourceData))

Classmethod factories have the added advantage that they are inheritable. You can now create a subclass of Foo, and the inherited factory method would then produce instances of that subclass.

With a choice between a function and a class method, I'd choose the class method. It documents quite clearly what kind of object the factory is going to produce, without having to make this explicit in the function name. This becomes much clearer when you not only have multiple factory methods, but also multiple classes.

Compare the following two alternatives:

foo.Foo.fromFrobnar(...)
foo.Foo.fromSpamNEggs(...)
foo.Foo.someComputedVersion()
foo.Bar.fromFrobnar(...)
foo.Bar.someComputedVersion()

vs.

foo.createFooFromFrobnar()
foo.createFooFromSpamNEggs()
foo.createSomeComputedVersionFoo()
foo.createBarFromFrobnar()
foo.createSomeComputedVersionBar()

Even better, your end-user could import just the Foo class and use it for the various ways you can create it, as you have all the factory methods in one place:

from foo import Foo
Foo()
Foo.fromFrobnar(...)
Foo.fromSpamNEggs(...)
Foo.someComputedVersion()

The stdlib datetime module uses class method factories extensively, and it's API is much the clearer for it.

Python – Why doesn’t Python have a “flatten” function for lists

Proposals for a flatten function to be added to the standard library appear from time to time on python-dev and python-ideas mailing lists. Python developers usually respond with the following points:

A one-level flatten (turning an iterable of iterables into a single iterable) is a trivial one-line expression (x for y in z for x in y) and in any case is already in the standard library under the name itertools.chain.from_iterable.
What are the use cases for a general-purpose multi-level flatten? Are these really compelling enough for the function to be added to the standard library?
How would a general-purpose multi-level flatten decide when to flatten and when to leave alone? You might think that a rule like "flatten anything that supports the iterable interface" would work, but that would lead to an infinite loop for flatten('a').

See for example Raymond Hettinger:

It has been discussed ad nauseam on comp.lang.python. People seem to enjoy writing their own versions of flatten more than finding legitimate use cases that don't already have trivial solutions.

A general purpose flattener needs some way to be told what is atomic and what can be further subdivided. Also, it is not obvious how the algorithm should be extended to cover inputs with tree-like data structures with data at nodes as well as the leaves (preorder, postorder, inorder traversal, etc.)

Best Answer

Related Solutions

Python Design – Best Practices for Python Factory Functions

Python – Why doesn’t Python have a “flatten” function for lists

Related Topic