Answer to Question #92392 in Python for AKHILA

Question

Consider the following function f.

def f(m):
if m == 0:
return(0)
else:
return(m+f(m-1))
Which of the following is correct?

The function always terminates with f(n) = factorial of n
The function always terminates with f(n) = n(n+1)/2
The function terminates for non­negative n with f(n) = factorial of n
The function terminates for non­negative n with f(n) = n(n+1)/2

Answer 1

This function uses recursion to produce the results - in the return statement it calls itself.

If m is negative, then recursion will never stop - because f(0) cannot be reached.

For nonnegative numbers you can rewrite this function like this: f(m) = m + f(m - 1), f(0) = 0

For instance, for m = 3:

f(3) = 3 + f(2) = 3 + (2 + f(1)) = 3 + (2 + (1 + f(0))) = 3 + 2 + 1

so for any nonnegative number: f(n) = n + (n - 1) + (n - 2) + ... + 1 = n(n + 1)/2

You can read about how to calculate the sum n + (n - 1) + (n - 2) + ... + 1 here:

https://mathcentral.uregina.ca/qq/database/qq.02.06/jo1.html

Also note, that in the real world recursion has a limit - you cannot make arbitrary number of recursions.

So if m is large enough, f(m) will throw an exception: "RecursionError: maximum recursion depth exceeded in comparison"

On my machine the recursion limit is 1000.

So, the correct answer is number 4: The function terminates for non­negative n with f(n) = n(n+1)/2