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

Question

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?

Answer 1

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.