3
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?

ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152
kalin
  • 155
  • 9

3 Answers3

3

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.

BartoszKP
  • 34,786
  • 15
  • 102
  • 130
3

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.

ivan_pozdeev
  • 33,874
  • 19
  • 107
  • 152
  • Is a tail-recursive function written in a language implementing TCO no longer recursive? Its footprint is no longer proportional to depth, after all. – Charles Duffy Nov 13 '14 at 01:42
  • TCO is but internal optimization. Is an unrolled loop still a loop? Anyway, do you see any other way to put the distinctive difference between iteration and recursion? – ivan_pozdeev Nov 13 '14 at 21:28
  • As someone who's had my head in the general vicinity of Haskell for at least some short period of time, I'm tempted to think of functions as pure mathematical constructs, decoupling the properties of their definitions from those of any associated runtime implementation. – Charles Duffy Nov 13 '14 at 21:53
  • I think I've got it - the way to put the distinction. – ivan_pozdeev Nov 13 '14 at 22:07
0

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.

Enrico Granata
  • 3,303
  • 18
  • 25
  • 3
    Using a stack does not make a function recursive. A stack is just the data structure that most, if not all, languages use to handle nested function calls, of which recursive calls are just one type. – chepner Nov 12 '14 at 21:52
  • I wouldnt dismiss this answer straight away. According to the definition of recursive, it is "involving the repeated application of a rule, definition, or procedure to successive results." It doesnt have any mention of needing to call itself to be considered recursive. A stack structure seems to be a good way to help conceptualise the idea of recursion without the function calling itself. Am i wrong? – kalin Nov 12 '14 at 22:02
  • @kalin, a stack structure is how recursion is _actually_ implemented -- look at how the call stack (on which recursion depends) is implemented. So it's not just a useful concept, it's how the real thing is implemented too. – Charles Duffy Nov 12 '14 at 22:04
  • @kalin That's not a very good definition of "recursive", then, as that definition could easily apply to "iterative", and does nothing to capture the usual notion of "self-referencing" that "recursive" implies... – twalberg Nov 12 '14 at 22:04
  • @CharlesDuffy so this answer shouldnt be getting downvoted, right? do you have any comments on the other answer to this question by Bartosz? – kalin Nov 12 '14 at 22:05
  • @twalberg i thought the keywords in the definition i gave were "to successive results". An iterative procedure doesnt work on successive results, or does it? – kalin Nov 12 '14 at 22:07
  • @kalin The sum of the first `N` integers would naively be implemented by an iterative algorithm that simply adds the next integer "to successive results", at least if one is unaware of the shortcut `N * (N + 1) / 2`... Simply working with successive results in a sequence does not make something recursive. – twalberg Nov 12 '14 at 22:09
  • 1
    @kalin, well, the objections are true, to a point -- using a stack (or equivalent) is necessary but not sufficient for a conventional recursive function implementation. It's a balancing act in terms of whether that objection makes this a bad answer; personally, I don't think it is. That said, I would agree with the objections (only) inasmuch as to adopt a definition of "recursive" that allows functions that don't call themselves to be considered _explicitly recursive_, rather than _demonstrative of recursion_, would be to rob the word of some portion of its understood meaning. – Charles Duffy Nov 12 '14 at 22:26
  • How to pass arguments or how to get values back are not part of the CPU so it is emulated, perhaps by one of the many standard recommendations. Recursion without arguments is wastful so in a way recursion isn't a part of the CPU. In the function you push arguments to a stack before call/jmp and the cleanup is done afterwards. C/anylang does it for you but it still needs to be instructions to do just that manually. Functions as we know it are emulated, just like this "recursion" by user stack. – Sylwester Nov 12 '14 at 22:59
  • The question is weather the *function* itself is recursive. I'd agree that the algorithm it implements can be called recursive, in some, not very common, but acceptable meaning. But that doesn't make this function recursive. In the same way the fact that this function uses a stack doesn't imply that this function is a stack ;) – BartoszKP Nov 22 '14 at 16:14