Getting started with recursion

Question

I need to write a function that is the recursive version of summing up numbers 1 through n. It needs to be recursive, which I have no idea how to do, although I did the iterative version quite easily.

All I know about recursion is that you call the function in the function. Any help on where to get started is greatly appreciated.

Here is the iterative version I did.

def summ(n):
    result = 0
    for i in range(1,n+1,1):
        result = result + i
    return result

When thinking about recursion, I've always found it helpful to formulate an English sentence for how my recursion works. In this case I might say something like "The sum from 1 to n can be described as: n plus the sum of 1 to n-1." While you still have to define base cases and such, I've always found a good sentence helps me visualize the execution. — Wilduck
– Wilduck, Commented Nov 22, 2011 at 19:29

Fred Foo · Accepted Answer · 2011-11-22 18:41:24Z

5

As always with recursive functions, define a base case and a recursive case, then implement these in a function that checks whether it's reached the base case. There are various recursive algorithms for this problem, one of which is:

Base case. n==1. The sum is trivial.

Recursive case. If you have the sum of the numbers through n, how do you get the sum through n+1?

edited Nov 22, 2011 at 18:41

answered Nov 22, 2011 at 18:35

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Manny D Over a year ago

Depending on how you want your function to handle values less than 1, I'd say the base case should be n <= 1.

Fred Foo Over a year ago

@MannyD: the OP wants to sum "numbers 1 through n". In practice, I'd just write sum(xrange(n+1)).

Manny D Over a year ago

Yeah I'm always thinking error cases and if you call your function with 0 or less, you'd best be prepared to handle it otherwise you might have your function infinitely recur on itself. In normal cases, yes, that base case would be sufficient.

matehat · Accepted Answer · 2011-11-22 18:42:32Z

2

Recursion happens when a function, in order to calculate its own result, calls itself with modified arguments and waits for that function call to return before continuing the calculation. That other function call might then call itself again with other modified arguments, and so recursion continue until it hits a case where the function does not need to call itself to calculate its result, and this case is called the base case. For summing numbers from 1 to N, the base case can obviously be for the number 1. Translating that to code, you would have something like :

def addup(n):
  if n == 1:
    return 1
  else:
    new_n = # the new N which needs to be passed to the recursion
    return n+addup(new_n)

answered Nov 22, 2011 at 18:42

matehat

5,3743 gold badges32 silver badges42 bronze badges

Comments

Tich · Accepted Answer · 2012-03-19 13:42:42Z

1

I think this answer is in order,using the base case as m==1

def summ(m):
    if m==1:
        return 1
    else:
        return m+summ(m-1)

answered Mar 19, 2012 at 13:42

Tich

111 bronze badge

Collectives™ on Stack Overflow

Getting started with recursion

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related