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)

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

thank you very much