CODEWITHSUNDEEP
pythonrecursion
kalin
kalin

Reputation: 155

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?

Upvotes: 3

Views: 575

Answers (3)

BartoszKP
BartoszKP

Reputation: 35891

You are right that this particular function is not recursive. However, the context is, that on the previous slide there was a recursive function, and in this one they want to show a glimpse of how it behaves internally. They later say:

The previous example [i.e. the one in question - B.] gives us some insight into how Python implements a recursive function call.

So, yes, the title is misleading, it should be rather Expanding a recursive function or Imitating recursive function behavior with a stack or something like this.

One may say that this function employs a recursive approach/strategy in some sense, to the problem being solved, but is not recursive itself.

Upvotes: 3

ivan_pozdeev
ivan_pozdeev

Reputation: 35998

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.

Upvotes: 3

Enrico Granata
Enrico Granata

Reputation: 3329

Because you're using a stack structure.

If you consider how function calling is implemented, recursion is essentially an easy way to get the compiler to manage a stack of invocations for you.

This function does all the stack handling manually, but it is still conceptually a recursive function, just one where the stack management is done manually instead of letting the compiler do it.

Upvotes: 0

Related Questions