CODEWITHSUNDEEP
python-3.xrecursion
Vinay Patel
Vinay Patel

Reputation: 25

Python infinite recursion with formula

### Run the code below and understand the error messages
### Fix the code to sum integers from 1 up to k
### 

def f(k):
    return f(k-1) + k
print(f(10))

I am confused on how to fix this code while using recursion, I keep getting the error messages
[Previous line repeated 995 more times] RecursionError: maximum recursion depth exceeded Is there a simple way to fix this without using any while loops or creating more than 1 variable?

Upvotes: 2

Views: 11436

Answers (4)

ksha
ksha

Reputation: 2087

A recursion should have a termination condition, i.e. the base case. When your variable attains that value there are no more recursive function calls. e.g. in your code,

def f(k):
    if(k == 1): 
        return k
    return f(k-1) + k
print(f(10))

we define the base case 1, if you want to take the sum of values from n to 1. You can put any other number, positive or negative there, if you want the sum to extend upto that number. e.g. maybe you want to take sum from n to -3, then base case would be k == -3.

Upvotes: 3

Krish
Krish

Reputation: 1081

You are working out the sum of all of all numbers from 1 to 10 which in essence returns the 10th triangular number. Eg. the number of black circles in each triangle

Using the formula on OEIS gives you this as your code.

def f(k):
    return int(k*(k+1)/2)
print(f(10))

How do we know int() doesn't break this? k and k + 1 are adjacent numbers and one of them must have a factor of two so this formula will always return an integer if given an integer.

Upvotes: 0

Rob Gwynn-Jones
Rob Gwynn-Jones

Reputation: 687

Your recursion never terminates. You could try:

def f(k):
    return k if k < 2 else f(k-1) + k
print(f(10))

Upvotes: 0

pathik devani
pathik devani

Reputation: 530

Python doesn't have optimized tail recursion. You f function call k time. If k is very big number then Python trow RecursionError. You can see what is limit of recursion via sys.getrecursionlimit and change via sys.setrecursionlimit. But changing limit is not good idea. Instead of changing you can change your code logic or pattern.

Upvotes: 1

Related Questions