Is it possible to convert a recursive function like the one below to a completely iterative function?

def fact(n):
    if n <= 1:
        return
    for i in range(n):
        fact(n-1)
        doSomethingFunc()

It seems pretty easy to do given extra space like a stack or a queue, but I was wondering if we can do this in O(1) space complexity?

Note, we cannot do something like:

def fact(n):
    for i in range (factorial(n)):
        doSomethingFunc()

since it takes a non-constant amount of memory to store the result of factorial(n).

CodePudding user response：

Well, generally speaking no. I mean, the space taken in the stack by recursive functions is not just an inconvenient of this programming style. It is the memory needed for the computation.

So, sure, for lot of algorithm, that space is unnecessary and could be spared. For a classical factorial for example

def fact(n):
    if n<=1:
        return 1
    else:
        return n*fact(n-1)

the stacking of all the n, n-1, n-2, ..., 1 arguments is not really necessary. So, sure, you can find an implementation that get rid of it. But that is optimization (For example, in the specific case of terminal recursion. But I am pretty sure that you add that "doSomething" to make clear that you don't want to focus on that specific case). You cannot assume in general that an algorithm that don't need all those values exist, recursive or iterative. Or else, that would be saying that all algorithm exist in a O(1) space complexity version.

Example: base representation of a positive integer

def baseRepr(num, base):
    if num>=base:
        s=baseRepr(num//base, base)
    else:
        s=''
    return s chr(48 num