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:
n == 0factorial(n - 1)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.
Recursive function example:
def recursive(string, num):
print "#%s - %s" % (string, num)
recursive(string, num+1)
Run it with:
recursive("Hello world", 0)
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.
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:
n == 0factorial(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
Recursive function example:
def recursive(string, num):
print "#%s - %s" % (string, num)
recursive(string, num+1)
Run it with:
recursive("Hello world", 0)
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
Recursive function example:
def recursive(string, num):
print "#%s - %s" % (string, num)
recursive(string, num+1)
Run it with:
recursive("Hello world", 0)
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.
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
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:
n == 0factorial(n - 1)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.
Source: Stackoverflow.com