I used return, however the recursion does not end. help me please

user_17059744 0
Viewed 53

I am doing a question that gives me a start coordinate, a end coordinate and the number of times of moving.Every time you can add 1 or minus 1 to x or y coordinate based on previous coordinate and the number of moving limit the time the coordinate can move. At last, I need to identify whether there is a possibility to get to the end coordinate

I decide to use recursion to solve this problem however, it does not end even if I wrote return inside a if else statement. Do you mind to take a look at it. This is the code

# https://cemc.uwaterloo.ca/contests/computing/2017/stage%201/juniorEF.pdf
# input
start = input()
end = input()
count = int(input())

coo_end = end.split(' ')
x_end = coo_end[0]
y_end = coo_end[1]
end_set = {int(x_end), int(y_end)}

#processing
coo = start.split(' ')
x = int(coo[0])
y = int(coo[1])

change_x = x
change_y = y
sum = x + y+count

set1 = set()
tim = 0
timer = 0

ways =  4** (count-1)


def elit(x, y, tim,timer, ways = ways):
    print(tim,timer)
    tim = tim +1
    co1 = (x, y+1)
    co2 = (x+1,  y)
    co3 = (x, y-1)
    co4 = (x-1, y)
    if tim == count:
        tim =0
        set1.add(co1)
        set1.add(co2)
        set1.add(co3)
        set1.add(co4)
        print(timer)
        timer = timer  +1
        if timer == ways:
            print('hiii')
            return co1, co2, co3, co4 #### this is the place there is a problem
        
    elit(co1[0],co1[1],tim,timer)
    elit(co2[0],co2[1],tim,timer)
    elit(co3[0],co3[1],tim, timer)
    elit(co4[0],co4[1],tim, timer)





#print(elit(change_x,change_y,tim)) - none why
elit(change_x,change_y,tim, timer)
#print(list1)

for a in set1:
    if end_set != a:
        answer = 'N'
        continue
    else:
        answer = "Y"
        break
print(answer)

In addition, if you have any suggestions about writing this question, do you mind to tell me since I am not sure I am using the best solution.

one of example is Sample Input 3 4 (start value) 3 3 (end value) 3 (count) Output for Sample Input Y Explanation One possibility is to travel from (3, 4) to (4, 4) to (4, 3) to (3, 3).

the detailed question can be seen in this file https://cemc.uwaterloo.ca/contests/computing/2017/stage%201/juniorEF.pdf It is question 3. Thank you

thank you guys

recursion function python
1 Answers

the function is returning properly however by the time you reach the recursive depth to return anything you have called so many instances of the function that it seems like its in an infinite loop

when you call elite the first time the function calls itself four more times, in the example you have given timer is only incremented every 3 cycles and the function only return once timer hits 16 thus the function will need to run 48 times before returning anything and each time the function will be called 4 more times, this exponential growth means for this example the function will be called 19807040628566084398385987584 times, which depending on your machine may well take until the heat death of the universe

i thought i should add that i think you have somewhat over complicated the question, on a grid to get from one point to another the only options are the minimum distance or that same minimum with a diversion that must always be a multiple of 2 in length, so if t the movement is at least the minimum distance or any multiple of 2 over the result should be 'Y', the minimum distance will just be the difference between the coordinates on each axis this can be found by add in the difference between the x and y coordinates

abs(int(start[0]) - int(end[0])) + abs(int(start[1]) -int(end[1]))

the whole function therefore can just be:

def elit():
    start = input('start: ').split(' ')
    end = input('end: ').split(' ')
    count = int(input('count: '))
    distance = abs(int(start[0]) - int(end[0])) + abs(int(start[1]) -int(end[1]))
    if (count - distance) % 2 == 0:
        print('Y')
    else:
        print('N')

input:

3 4
3 3
3

output:

Y

input:

10 4
10 2
5

output:

N
user_155832490
Related