Recursive program optimization

Question

How to write a function countTo(n) that counts from 1 to n and prints each number without using explicit loops (only recursion)?

The solution must be asymptotically optimal in space and time, even without tail call optimisation, given arbitrarily big n.

Note: the optimal time complexity is O(1) while the optimal space complexity is O(log n) – even in the iterative case, since the (arbitrarily large) number needs to be printed.

The question comes from lesswrong.com, and the relevant details are taken from the discussion there (otherwise the question becomes impossible to answer since their original statement makes misleading assumptions).

@S.Lott As I said in my answer, Python does not perform tail call elimination, so this won't help him. In the context of Python the answer to this question is "No". — sepp2k
– sepp2k, Commented Feb 12, 2012 at 19:49
The guys from LessWrong are sometimes … well … difficult. Let me just point to the comment thread explaining the intricacies of the problem. Simply put, the original interview question is stated wrongly. It only admits a solution once the question is stated more carefully. — Konrad Rudolph
– Konrad Rudolph, Commented Feb 12, 2012 at 20:56
I’ve completely restated the question to reflect the originally intended question, rather than the one that was actually asked. Unfortunately, this means that all answers are now irrelevant but otherwise the question is trivially answered and rather boring. @genesiss, I hope that’s OK. It wasn’t your fault, by the way, the original formulation on LessWrong was wrong. — Konrad Rudolph
– Konrad Rudolph, Commented Feb 12, 2012 at 21:14

sepp2k · Accepted Answer · 2012-02-12 19:36:19Z

5

If you want the rewritten version to still be recursive, there is no way. Any function call will consume stack space.

There are languages in which calls that are in a tail position will not consume stack space. In such languages you could rewrite your function to be tail-recursive, so it would run in O(1) space. However Python is not one of those languages.

answered Feb 12, 2012 at 19:36

sepp2k

372k56 gold badges687 silver badges687 bronze badges

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

7 Comments

apc Over a year ago

Why can't you use a CPS-based Python implementation?

user395760 Over a year ago

@apc In thoery, you can. But practically, all CPS-based Python implementations are in obscurity. If you want your Python code to be remotely portable, you do not rely on tail recursion optimization.

apc Over a year ago

@delnan, I could be wrong, but I believe PyPy supports it via RPython. The portability issue seems like a salient point, but what specific portability issues are known to occur?

user395760 Over a year ago

@apc Either you express yourself unclearly, or you have some misconceptions about PyPy. The "default" builds of PyPy (both JIT and non-JIT) don't feature anything remotely stackless. There is an optional stackless build, but (1) few people both to install it, (2) an SO question a while ago indicates it doesn't do tail call optimization but only offers some primitives that can be used to that effect, and (3) I remember at least one nasty stackless-exclusive bug. But even if all PyPy binaries has TCO, PyPy isn't terribly widespread either.

sepp2k Over a year ago

@apc Ignoring whether or not any existing Python implementation eliminates tail calls, Guido van Rossum said that "the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it". So any implementation that does eliminate tail call wouldn't be a strict implementation of Python.

|

dan04 · Accepted Answer · 2012-02-12 19:35:31Z

1

Use iteration instead of recursion.

def countTo(n):
    for i in range(1, n + 1):
        print(n)

answered Feb 12, 2012 at 19:35

dan04

92k23 gold badges169 silver badges206 bronze badges

1 Comment

Uros K Over a year ago

Program must stay recursive. I added that to the question.

Voo · Accepted Answer · 2012-02-12 19:52:23Z

1

If python supported tail recursion you could do this:

def foo(n):
    print n
    if n > 1:
        foo(n-1)

The corresponding c program with any modern gcc version would run in O(1). I'm not aware of any python interpreter that supports tail recursion though - but I don't see any limitations from the language itself that would forbid it.

answered Feb 12, 2012 at 19:52

Voo

30.4k13 gold badges91 silver badges165 bronze badges

2 Comments

sepp2k Over a year ago

That would print the numbers in the wrong order though. To create a tail-recursive version, you'd need two arguments.

Voo Over a year ago

@sepp2k I somehow got the idea that we should count from n to 1.. no idea why. But the other solution should be pretty obvious as well and is left as an exercise to the reader I think ;)

Gangnus · Accepted Answer · 2012-02-12 21:30:43Z

0

def foo(n):
    if n > 1:
        foo(n-1)
    print n

(Take it as algorithm, not language -specific code.)

The time complexity here will be O(n*log(n)), if we take that printing of every digit takes the same time.

answered Feb 12, 2012 at 21:30

Gangnus

24.6k17 gold badges99 silver badges158 bronze badges

Collectives™ on Stack Overflow

Recursive program optimization

4 Answers 4

7 Comments

1 Comment

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

7 Comments

1 Comment

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related