How can I build a recursive function in python? [duplicate]

I'm wondering whether you meant "recursive". Here is a simple example of a recursive function to compute the factorial function:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

The two key elements of a recursive algorithm are:

The termination condition: n == 0
The reduction step where the function calls itself with a smaller number each time: factorial(n - 1)

Recursion in Python works just as recursion in an other language, with the recursive construct defined in terms of itself:

For example a recursive class could be a binary tree (or any tree):

class tree():
    def __init__(self):
        '''Initialise the tree'''
        self.Data = None
        self.Count = 0
        self.LeftSubtree = None
        self.RightSubtree = None

    def Insert(self, data):
        '''Add an item of data to the tree'''
        if self.Data == None:
            self.Data = data
            self.Count += 1
        elif data < self.Data:
            if self.LeftSubtree == None:
                # tree is a recurive class definition
                self.LeftSubtree = tree()
            # Insert is a recursive function
            self.LeftSubtree.Insert(data)
        elif data == self.Data:
            self.Count += 1
        elif data > self.Data:
            if self.RightSubtree == None:
                self.RightSubtree = tree()
            self.RightSubtree.Insert(data)

if __name__ == '__main__':
    T = tree()
    # The root node
    T.Insert('b')
    # Will be put into the left subtree
    T.Insert('a')
    # Will be put into the right subtree
    T.Insert('c')

As already mentioned a recursive structure must have a termination condition. In this class, it is not so obvious because it only recurses if new elements are added, and only does it a single time extra.

Also worth noting, python by default has a limit to the depth of recursion available, to avoid absorbing all of the computer's memory. On my computer this is 1000. I don't know if this changes depending on hardware, etc. To see yours :

import sys
sys.getrecursionlimit()

and to set it :

import sys #(if you haven't already)
sys.setrecursionlimit()

edit: I can't guarentee that my binary tree is the most efficient design ever. If anyone can improve it, I'd be happy to hear how

Let's say you want to build: u(n+1)=f(u(n)) with u(0)=u0

One solution is to define a simple recursive function:

u0 = ...

def f(x):
  ...

def u(n):
  if n==0: return u0
  return f(u(n-1))

Unfortunately, if you want to calculate high values of u, you will run into a stack overflow error.

Another solution is a simple loop:

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  return ux

But if you want multiple values of u for different values of n, this is suboptimal. You could cache all values in an array, but you may run into an out of memory error. You may want to use generators instead:

def u(n):
  ux = u0
  for i in xrange(n):
    ux=f(ux)
  yield ux

for val in u(1000):
  print val

There are many other options, but I guess these are the main ones.

How can I build a recursive function in python? [duplicate]

Related

Recent Posts