Detecting Infinite recursion in Python or dynamic languages

Question

Recently I tried compiling program something like this with GCC:

int f(int i){
    if(i<0){ return 0;}
    return f(i-1);
f(100000);

and it ran just fine. When I inspected the stack frames the compiler optimized the program to use only one frame, by just jumping back to the beginning of the function and only replacing the arguments to f. And - the compiler wasn't even running in optimized mode.

Now, when I try the same thing in Python - I hit maximum recursion wall (or probably stack overflow if i set recursion depth too high).

Is there way that a dynamic language like python can take advantage of these nice optimizations? Maybe it's possible to use a compiler instead of an interpreter to make this work?

Just curious!

Answer 1

It has nothing to do with the fact that it is a dynamic language or that it is interpreted. CPython just doesn't implement Tail Recursion optimization. You may find that JPython etc do.

Answer 2

When I inspected the stack frames the compiler optimized the program to use only one frame, by just jumping back to the beginning of the function and only replacing the arguments to f.

What you're describing is called "tail recursion". Some compilers/interpreters support it, some don't. Most don't, in fact. As you noticed, gcc does. And in fact, tail recursion is a part of the spec for the Scheme programming language, so all Scheme compilers/interpreters must support tail recursion. On the other hand, the compilers for languages like Java and Python (as well as most other languages, I'd wager) don't do tail recursion.

Is there way that a dynamic language like python can take advantage of these nice optimizations?

Do you mean, right now, or are you asking in more abstract terms? Speaking abstractly, yes! It would absolutely be possible for dynamic languages to take advantage of tail recursion (Scheme does, for example). But speaking concretely, no, CPython (the canonical Python interpreter) doesn't have a flag or other parameter to enable tail recursion.

Answer 3

The optimisation you're talking about is known as tail call elimination - a recursive call is unfolded into an iterative loop.

There has been some discussion of this, but the current situation is that this will not be added, at least to cpython proper. See Guido's blog entry for some discussion.

However, there do exist some decorators that manipulate the function to perform this optimisation. They generally only obtain the space saving though, not time (in fact, they're generally slower)

Answer 4

The following code contains a recursion function which is giving an error: I think the problem is the len(childLinks)==0 which cant be true bcoz web page will definately contain link so len of childLinks will never be zero and this recursive function will go into infinite loop.What should i do in order to come out of the infinite loop.

import sgmllib

import urllib, sgmllib

import sys

sys.setrecursionlimit(1000)

class Parser(sgmllib.SGMLParser):

def parse(self, s):
    "Parse the given string 's'."
    self.feed(s)
    self.close()

def __init__(self, verbose=0):
    "Initialise an object, passing 'verbose' to the superclass."
    sgmllib.SGMLParser.__init__(self, verbose)
    self.hyperlinks = []
    self.inside_a_element = 0

def start_a(self, attributes):
    "Process a hyperlink and its 'attributes'."

    for name, value in attributes:
        if name == "href":
            self.hyperlinks.append(value)
            self.inside_a_element = 1

def end_a(self):
    "Record the end of a hyperlink."
    self.inside_a_element = 0

def get_hyperlinks(self):
    "Return the list of hyperlinks."
    return self.hyperlinks

def process_page(self, parentNode):

    print "parent :: ", parentNode.nodeName

    file= urllib.urlopen(parentNode.nodeName)
    data = file.read()
    parser = Parser()
    parser.parse(data)
    childLinks = parser.get_hyperlinks()
    if len(childLinks) == 0:
        print "Leaf Node :: ", parentNode.nodeName
        return

    for childLink in childLinks:
        childNode = Node(childLink)
        parentNode.addChild(childNode)
        print "   Child :: ", childNode.nodeName
        self.process_page(childNode)

class Node(object):

def __init__(self, nodeName=None, children=[]):
    self.nodeName = nodeName
    self.children = children


def print_info(self):
    print "RootNode", "<" + self.rootNode + ">"

def getNodeName(self):
    return nodeName

def setNodeName(self,value):
    self.nodeName=value

def getParentNode(self):
    return parentNode

def setChildren(children):
    self.children=children

def addChild(self, child):
    self.children.append(child)

def getChildren(self):
    return children

def setRootNode(self,rootNode):
     self.rootNode="d://PythonSample/Page.html"

def getRootNode(self):
    return self.rootNode

def getFirstChild():
    firstChild=Node("d://PythonSample/Page.html")
    return firstChild

class TreeCreator:

def __init__(self, startURL):
    self.startURL = startURL

def createTree(self):
    parser=Parser()
    node = Node(startURL)
    parser.process_page(node)
    return node

def printTree(self, node):
    print node.nodeName
    children = node.children

    if len(children) == 0 :
        return

    for childNode in children:
        print "   ->" ,childNode.nodeName
        #self.printTree(childNode)

if name == 'main':

startURL="http://ocado.com"  
treeCreator =TreeCreator(startURL)
nodeTree = treeCreator.createTree()
treeCreator.printTree(nodeTree);

Kindly suggest something.