CODEWITHSUNDEEP
pythonrecursion
Neemaximo
Neemaximo

Reputation: 20831

Getting started with recursion

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

Upvotes: 1

Views: 208

Answers (3)

Tich
Tich

Reputation: 11

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)

Upvotes: 1

matehat
matehat

Reputation: 5374

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)

Upvotes: 2

Fred Foo
Fred Foo

Reputation: 363787

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?

Upvotes: 5

Related Questions