Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
152 views
in Technique[技术] by (71.8m points)

python - Is this function recursive even though it doesn't call itself?

from pythonds.basic.stack import Stack

rStack = Stack()

def toStr(n,base):
    convertString = "0123456789ABCDEF"
    while n > 0:
        if n < base:
            rStack.push(convertString[n])
        else:
            rStack.push(convertString[n % base])
        n = n // base
    res = ""
    while not rStack.isEmpty():
        res = res + str(rStack.pop())
    return res

print(toStr(1345,2))

I'm referring to this tutorial and also pasted the code above. The tutorial says the function is recursive but I don't see a recursive call anywhere, just a while loop. What am I missing?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

A recursive algorithm, by definition, is a method where the solution to a problem depends on solutions to smaller instances of the same problem.

Here, the problem is to convert a number to a string in a given notation.

The "stockpiling" of data the function does actually looks like this:

push(d1)
push(d2)
...
push(dn-1)
push(dn)

res+=pop(dn)
res+=pop(dn-1)
...
res+=pop(d2)
res+=pop(d1)

which is effectively:

def pushpop():
    push(dx)
    pushpop(dx+1...dn)
    res+=pop(dx)

I.e. a step that processes a specific chunk of data encloses all the steps that process the rest of the data (with each chunk processed in the same way).

It can be argued if the function is recursive (since they tend to apply the term to subroutines in a narrower sense), but the algorithm it implements definitely is.


For you to better feel the difference, here's an iterative solution to the same problem:

def toStr(n,base):
    charmap = "0123456789ABCDEF"
    res=''
    while n > 0:
        res = charmap[n % base] + res
        n = n // base
    return res

As you can see, this method has much lower memory footprint as it doesn't stockpile tasks. This is the difference: an iterative algorithm performs each step using the same instance of the state by mutating it while a recursive one creates a new instance for each step, necessarily stockpiling them if the old ones are still needed.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...