Can you help me please? it'is importent

Python Help
1

i want to write this code in iterative version but i dont know how ?
def guess(x, y):
if x==y:
return x
elif x>y:
return guess(x-1, y)+guess(x, y+1)
else: return guess(x+1, y)+guess(x, y-1)

2

Please put code between “code fences”, lines of triple backticks, eg:

 ```
 your code
 goes here
 ```

There’s a </> button in the editor toolbar to make such a section.

That said, and restating your code to show indentation:

 def guess(x, y):
     if x==y:
         return x
     elif x>y:
         return guess(x-1, y)+guess(x, y+1)
     else: return guess(x+1, y)+guess(x, y-1)

This algorithm branches out. So absent a funky restatement of the
problem, you inherently need to store the “pending tasks” somewhere. In
a recursive solution (like your guess() function above) we store this
in the call stack just by calling the function recursively.

One reason to avoid that is that the stack is normally of limited size.
If your algorithm has a call depth of, say O(log(n)) that’s often ok,
but your algorithm above has a call depth of O(n) (where n seems to be
abs(x-y)) so using the stack easily becomes unreasonable.

The O() notation above is “big O notation”, an indication of the scale
of how expensive an algorithm is in time or space (often time).
A run time of O(log(n)) says that the algorithm tends to take time
that’s logarithmic compared to the data size,
See: Big O notation - Wikipedia

NB: I was talking about call depth aka stack size and therefore talking
about space, not time, as the size of the stack can be the limiting
factor.

FYI, Python raises a RecursionError if you run an infinitly recursive
function i.e. one which doesn’t have a termination case (your x==y
case) or doesn’t find it. But there’s nothing magic about that
exception, Python just has a limit on the stack size and if you exceed
it it raises the exception.

So, how to restructure things?

The usual approach is to store the outstanding tasks in some way. I
often use a list.

Let’s think about what your function does:

  • compare 2 numbers x and y; if they’re the same, the result is one
    of them
  • otherwise bring the numbers closer together by 1 in each direction
    (x or y), solve each of those, then add the solutions together

Doing that iteractively requires having some kind of data structure
representing the outstanding work, and pulling off pieces of that work
in little chunks until the outstanding work is empty.

The function becomes “iterative” because (a) it doesn’t call itself and
(b) instead just iterates over the outstanding work until it is all done.

Does that make sense?

We can approach your problem as a kind of long running sum of values.

When a pair of values is the same, add one of them to the total.
Otherwise queue “closer” pairs as outtanding, as as each pair reaches
equality, add it to the total. (Because that adds both “closer” flavours
to the total, this is the same as “solving both sides and adding them
together”.)

So let’s make a total:

 total = 0

and a list of the outstanding values:

 outstanding = [x, y]

You’re done when there are no more values to work with.

 while len(outstanding) > 0:

If there are values to work with, pull the first pair off the list:

     x = outstanding.pop()
     y = outstanding.pop()

The list is now 2 shorter.

When they’re the same, add x to the total.

     if x == y:
         total += x

The list remains shorter.

Otherwise, append the “closer pairs” to the outstanding work:

     else:
         if x > y:
             outstanding.extend( (x-1, y) )
             outstanding.extend( (x, y+1) )
         else:
             outstanding.extend( (x+1, y) )
             outstanding.extend( (x, y-1) )

The list is now 4 elements longer on this branch. This is the logical
equivalent of your recursive calls to guess(x-1,y) and friends.

However, eventually those pairs become equal and you start reducing the
amount of outstanding work instead of increasing it.

Eventually the list empties and the while len(outstanding) > 0 becomes
false, and the loop ends. Return the total.

 return total

All the above is totally untested.

You need to understand it and implement it. And If I’m wrong, you
need to understand what I’ve done incorrectly and fix it.

I recommend making a guess2(x,y) function with your iterative
approach. You can check whether it works by running guess() and
guess2() with the same values and seeing if you get the same results.
Technically that only lets you check if they don’t produce the same
results, but if they’re that same for several different pairs your
confidence can increase.

Cheers,
Cameron Simpson cs@cskk.id.au

3

thank you very much