Sum of a sequence using recursion

Question

Sum of a sequence using recursion

Navigation

#1 by (1 votes)

1

The idea of the code is to take a function with the following parameters: start , stop , step . start indicates the first number, stop the last and step the difference between each number and the idea is to add the elements of the sequence.

For example, in the case of the following parameters: (2,5,2) the sequence would be 2,4 and the result would be 6. This is the code that occurred to me but it does not work correctly:

def recursive(start,stop,step):
    if start>=stop:
       return start
    else:
       return start+recursive(start+step,stop,step)

The code works well when start equals the value of stop as in the case of the parameters (2,6,2) but in the case of (2,5,2) the output is 2 + 4 +6 and the idea is that only add 2 + 4.

python python-3.x

asked by Felka98 28.06.2018 в 18:55

source

1 answer

Error Can not process attribute android: fillColor Error with pd.DataFrame.replace, can not convert unicode string to float

score 1 · Answer 1

The cause is in the conditional, imagine the case you mention, the sequence of calls would be:

recursive(2, 5, 2) , 2 > 5, then return 2 + recursive(2+2, 5, 2) .
recursive(4, 5, 2) , 4 > 5, then return 4 + recursive(4+2, 5, 2)
recursive(6, 5, 2) , 6 < = 5, then return 6.

Now we must understand how the recursion that basically behaves like a stack works, the first call to the function is the last one to return and it is from this that you get the result. When the first call to the function occurs, it returns 2 + recursive(2+2, 5, 2) but can not return until recursive(2+2, 5, 2) is completed and returns something that add to 2, the same happens with the following calls, so that the last call is the first to complete and return something and from there follow the chain backwards until you reach the first call.

That is, when the third call recursive(6, 5, 2) returns start (6), the second one can continue and returns 4 + 6) , when this occurs the first call can return and returns 2 + 10 for what we get 12.

The problem is that the third call should never have occurred, because 6 is greater than 5. One possible solution following your original idea is to modify the conditional and instead of comparing start compare start + step , for example:

def recursive(start,stop,step):
    sum_ = start + step
    if sum_ > stop:
        return start
    return start + recursive(sum_, stop, step)

>>> recursive(2, 5, 2)
6
>>> recursive(2, 6, 2)
12

From the above, one of the problems of recursion is derived, each recursive call implies the creation of a new frame in the call stack and the stack is not infinite, this may end up causing an overflow of the same (Stack Overflow ...) Keep in mind that Python does not optimize queue recursion (which is not your case anyway) as it also happens in other languages (although in the case of Python it is rather because Guido van Rossum does not appreciate recursion too much. ..) so if the function were recursive queue we would still have the same problem.

By default Python limits the recursive calls to 1000 to protect the C stack (its overflow means the end of bad forms of the interpreter and that's not good ...), it's a fairly conservative limit and we can elevate it with care using sys.setrecursionlimit although generally in these cases, opt for other approaches (iteration, memoization, etc) is a better idea.