How to determine the output of a complex recursive function manually

Question

Here's the recursive code:

def trace(a, b): if (a > b): return -1 elif (a == b): print (a * a) return a * a else: m = (a + b) / 2 return trace (a, m) + trace (m + 1, b) x=trace(1,4) 

while I'm not sure what this function should do, we must find the result x=trace(1,4) together with the value x manually (this means that we cannot use downtime to help us).

After some time, I determined that the function would print 1 and 12.25, which would be output when assigning x to trace(1,4) .

However, I don’t know how to determine what the value of X will be. Although the answer is -91.75, I have no idea how it was received (although I know how it will take a long time to come up with this answer, and I don’t sure how we can quickly come up with in a short period of time, for example, when writing an exam).

Thanks in advance for your help!

Answer 1

Firstly, I cheated. With my chest, here are a few pointers: The function is most definitely not intended for Python 3! The reason is the operator /. In Python 2, this led to integers in Python3, which results in floats. Therefore, bearing in mind this precondition, this is my solution:

The function is not complicated. The data type of each and every one of your variables is an integer! m will always be an integer. x is 30. The recursion level is three, which is equal to seven calls to your function (including the first). And here is how you do such things: take paper and pen and simply write down each step.

• Input: a = 1 and b = 4, which leads to the else part in your function ... there is no output yet. There m is calculated as (1 + 4) / 2. In my book 2.5. But this is rounded to 2 because we have integers. Then the recursion begins with two calls (1,2) and (3,4)
• Let's look at (1,2): a = 1 and b = 2. Again, there is no way out, and we go straight to the else part: m is calculated as 3/2, which is a good 1.5, rounded to 1. Again, two function calls with new parameters (1,1) and (2, 2). Note that both calls will now introduce part of the elif function, and each of them will produce an output signal and a return value. You can replace (1,1) with 1 and (2,2) with 4. The recursion is done here, and the trace call (1,2) is the result of 5. Let's look at another branch of the recursion.
• The input is a = 3 and b = 4, which leads to another pair of calls with the following parameters: (3.3) and (4.4). I think you should understand this now. The interesting part is to add all the return values ​​in the form in which they are provided.

As for the function: it sums all the squares of all integers between a and b.

Answer 2

take a look at these lines:

 m = (a + b) / 2 return trace(a, m) + ... 

these lines are executed only if b greater than a . This means that m will always be greater than a , and calling the first recursive function has exactly the same problem. For values a = 1 and b > a , m converges to 1 . Theoretically, recursion never ends, since m will never be 1.0 or less. However, the accuracy of float is limited, so there is a point (after many recursive calls) where the processor cannot differ m from 1.0 . At this point, elif (a == b): becomes true and stops the recursion. This does not explain why the result is -91.75 , but it shows why it is almost impossible to display all recursive calls on a chart or tree or sth. Hope this helps.