Recursion is beating me.

[Yeen]

I understand the basic principle of recursion, but I'm having trouble implementing it in practice.

I understand this first case perfectly fine. It works because n is constantly getting closer to 0.

def faculty(n):
    # Base case
    if n == 0:
        return 1
    # Recursive call
    else:
        return n * faculty(n-1)

print(faculty(3))

But say I want to calculate (1)+(1/2)+(1/3)+(1/4)+(1/5)+...+(1/n) . Using the below function I only get the very first part (0,1) and then it stops. Obviously it'll stop because it's <= 1. However, if I change it to "if n==1:" it never stops recurring, because n is never 1 (runtime error). I think the problem is that I need n to be 9 (in this example) after the first calculation, but how do I get n = 9 and at the same time get 1/9 as a result for the calculation? Does this make any sense to anyone? I fear I might be rambling :confused:

#n is always >= 1
def sum(n):
	if n <= 1:
		return n
	else:
		return 1 + sum(1/n-1)

print(sum(10))

I've got the same problem with trying to calculate 1*1 + 2*2 + 3*3 + 4*4 + n*n. The part-result(correct term?) differs from what I need n to be, and I have yet to figure out how to adjust for it.

My math skills have been degrading for a few years due very low usage. Harmonic numbers > me.

[Mathhax0r]

You can use helper functions, you know.

def harmonicSum(n):
      def realSum(p):
            if p > n:
                  return 0
            return 1/p + realSum(p+1)
      return realSum(1)

There's probably a more eloquent solution, but what works, works. It also allows you to modify the function slightly to get numbers of the form 1/j + 1/(j+1) + ... + 1/(k-1) + 1/k, though you probably don't need to.

EDIT: Wow, I can't believe I didn't think of it sooner. Just add backwards.

def harmonicSum(n):
      if n == 1:
            return 1
      return 1/n + harmonicSum(n-1)

Now that's simpler.

[Yeen]

Thanks! I had it all backwards. Messing around with sum(1/n) was a bad idea. Now I can focus on the other problem :)

[jbennet]

Not related to the problem in hand, but its worth noting the best real-world example of recursion ive ever seen is a method to handle the inorder traversal of a binary tree.

[Yeen]

Solved the second problem.

def cans(n):
	if n == 1:
		return 1
	else:
		return n*n + cans(n-1)

print(cans(4))

Why I was trying to mess with the + blabla(n-1) part I'll never know. It's so simple once you leave it alone.

Going to check out the inorder traversal of a binary tree now.

Thanks :)

[Ene Uran]

Note that recursive functions have a lot of stack overhead and are slow. There is a limit to recursions:
print( sys.getrecursionlimit() ) # --> usually 1000 default setting
which can be changed to limit x with:
sys.setrecursionlimit(x)

[Ene Uran]

Solved the second problem.

def cans(n):
	if n == 1:
		return 1
	else:
		return n*n + cans(n-1)

print(cans(4))

Why I was trying to mess with the + blabla(n-1) part I'll never know. It's so simple once you leave it alone.

Going to check out the inorder traversal of a binary tree now.

Thanks :)

Oh no, what is this? You are using tabs for your Python indentations, a very bad habit. Four spaces are the custom. If you use tabs, then sooner or later you will mix them with spaces and then you are at the mercy of the editor setting and can get hard to trace errors.

For instance DaniWeb gives you 8 spaces per tab and if you have a couple of nested blocks, your code will look like dung!