Convert python while loop to recursion

Question

Herbert attempts to climb the slope (Heffalumps are heavy), so each of his rushes gains him only 95% as much distance as his previous rush. This means that if his first rush gains him rush_height_gain metres, then his second rush will only gain him 0.95 * rush_height_gain metres, his third rush 0.95 * 0.95 * rush_height_gain metres, and so on. Fortunately, his back sliding reduces in the same way.

The traditional way to write the code is:

def num_rushes(slope_height, rush_height_gain, back_sliding):
''' Calculate how many rushes '''
import math    
current_height = 0
rushes = 0
i = 0
while current_height < slope_height:
    current_height += rush_height_gain * (0.95 ** i)
    if current_height < slope_height:
        current_height -= back_sliding * (0.95 ** i)
    rushes += 1
    i += 1
return rushes

ans = num_rushes(10, 10, 9) print(ans) #result: 1
ans = num_rushes(100, 15, 7) print(ans) #result: 19
ans = num_rushes(150,20,9) print(ans) #result: 22

Now we need to use recursion to improve the efficiency. The recursive code I wrote below didn't get the desired result as above. Please point out how to revise it.

def num_rushes(slope_height, rush_height_gain, back_sliding, current_height=0):


if (slope_height-current_height) < rush_height_gain:
    return 0
else: 
    
    current_height = current_height + 0.95*(rush_height_gain-back_sliding) 
    
    return num_rushes(slope_height, 0.95*rush_height_gain, 0.95*back_sliding, current_height) + 1

ans = num_rushes(10, 10, 9) print(ans)
ans = num_rushes(100, 15, 7) print(ans)
ans = num_rushes(150,20,9) print(ans) #wrong result - get 23

trincot · Accepted Answer · 2022-03-05 06:18:15Z

1

Your recursive version is doing the backslide before checking that the height is reached. This check should happen between the forward rush and the backslide, not after the backslide.

Here is a correction, which also avoids the extra parameter:

def num_rushes(slope_height, rush_height_gain, back_sliding):
    if slope_height <= rush_height_gain:
        return int(slope_height > 0)
    return 1 + num_rushes(slope_height - rush_height_gain + back_sliding, 
                          0.95 * rush_height_gain, 0.95 * back_sliding)

Note the base case: if the slope_height is zero, no step has to be taken and 0 should be returned. In all other cases where the forward rush reaches the height, 1 should be returned.

edited Mar 5, 2022 at 6:18

answered Mar 5, 2022 at 6:12

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Convert python while loop to recursion

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related