将 python while 循环转换为递归

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) 打印（ans）#result: 1
ans = num_rushes(100, 15, 7) 打印（ans）#result: 19
ans = num_rushes(150,20,9) 打印（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) 打印(ans)
ans = num_rushes(100, 15, 7) 打印(ans)
ans = num_rushes(150,20,9) print(ans) #错误结果 - 得到 23

Answer 1

您的递归版本在之前进行后退，检查是否达到高度。这个检查应该发生在前冲和后退之间，而不是后退之后。

这里更正一下，也避免了额外的参数：

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)

注意基本情况：如果 slope_height 为零，则无需采取任何步骤，应返回 0。其他所有向前冲达到高度的情况，都应该返回1。

将 python while 循环转换为递归

Convert python while loop to recursion

python

algorithm

recursion