I need to write a program that carries out a up and then a down recursion for a function and I am totally lost as to how to start. I have looked at the python documentation and found it more confusing than helpful. I would appreciate it if anyone can point me in the right direction regarding tutorials, and or documentation on the conventions for summation in python. thanks
-
1is this homework? what have you tried so far?jterrace– jterrace2012-02-09 03:02:36 +00:00Commented Feb 9, 2012 at 3:02
-
I really have no idea what you are trying to do? Is it to understand recursion? Recursively sum a sequence? What do you mean by "up" and "down" recursion?grieve– grieve2012-02-09 05:55:39 +00:00Commented Feb 9, 2012 at 5:55
-
I am trying to write code that will solve the up and down recursion relations for the spherical Bessel functionStripers247– Stripers2472012-02-09 22:10:10 +00:00Commented Feb 9, 2012 at 22:10
-
I would strongly recommend not trying to implement spherical Bessel functions yourself, scipy ships with solid well tested versions of these functions: docs.scipy.org/doc/scipy/reference/…Andrew Walker– Andrew Walker2012-02-09 23:56:51 +00:00Commented Feb 9, 2012 at 23:56
Add a comment
|
2 Answers
Writing recursive function can be tricky to get your head around, but there are good references for getting better at solving such problems. I would strongly recommend getting a copy of "A little schemer". Working in a language like scheme may be easier than coming straight to this in python.
In python, a recursive summation can be written as:
def rsum( seq ):
if not seq:
return 0
else:
return seq[0] + rsum(seq[1:])
Working from first principles, it is worth noting that this function follows a very common pattern, it is an example of a fold. In python you can write foldl and foldr as:
def foldl( f, z, xs ):
if not xs:
return z
else:
return foldl(f, f(z, xs[0]), xs[1:])
def foldr( f, z, xs ):
if not xs:
return z
else:
return f(xs[0], foldr(f, z, xs[1:]))
Using a higher order building block this means you can really write rsum as:
def rsum(seq):
return foldl( lambda a,b: a+b, 0, seq )
Or:
def rsum(seq):
return foldr( lambda a,b: a+b, 0, seq )
7 Comments
grieve
You can always use the built in sum. docs.python.org/library/functions.html#sum
Andrew Walker
Of course you can use the built in sum function, but that isn't what the question was.
Thomas K
Possibly relevant: I think foldl is equivalent to
functools.reduce, although that probably isn't implemented recursively.
Stripers247
@Andrew Walker. Thank you for the reply. How would one use a formula say (x^2+1) from x=0 to 10 for example in your example?
Andrew Walker
In the general case? I wouldn't use recursion. I'd simply use the builtin
sum and a generator expression: sum( ( x**2 + 1 for x in xrange(10) ) ). It wouldn't be wrong to use rsum as defined in the answer, but it would be significantly slower. |
Here is the official slides for Problem Solving with Algorithms and Data Structures:
http://www.pythonworks.org/pythonds/Slides.zip?attredirects=0&d=1
You can check Chapter 3, it's about recursion algorithm.
1 Comment
Stripers247
Thanks Tao I will check it out!