到达结束递归方法的最小跳数

Question

我有一个关于递归的小问题。下面的代码实际上是问题的答案到达终点的最小跳跃次数

// C program to find Minimum
// number of jumps to reach end
#include <limits.h>
#include <stdio.h>

// Returns minimum number of
// jumps to reach arr[h] from arr[l]
int minJumps(int arr[], int l, int h)
{
    // Base case: when source and destination are same
    if (h == l)
        return 0;

    // When nothing is reachable from the given source
    if (arr[l] == 0)
        return INT_MAX;

    // Traverse through all the points
    // reachable from arr[l]. Recursively
    // get the minimum number of jumps
    // needed to reach arr[h] from these
    // reachable points.
    int min = INT_MAX;
    for (int i = l + 1; i <= h && i <= l + arr[l]; i++) {
        int jumps = minJumps(arr, i, h);
        if (jumps != INT_MAX && jumps + 1 < min)
            min = jumps + 1;
    }

    return min;
}

// Driver program to test above function
int main()
{
    int arr[] = { 1, 3, 6, 3, 2, 3, 6, 8, 9, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    printf(
        "Minimum number of jumps to reach end is %d ",
        minJumps(arr, 0, n - 1));
    return 0;
}

当h==l和arr[l]==0时，函数返回sth，函数结束。否则，它将更新一个称为跳跃的变量，但我无法理解该语句。例如，当i=1或i=2时，跳跃的值是多少，依此类推。换句话说，我无法理解变量更新过程的意义。

Answer 1

也许关键是仔细阅读和理解函数的定义：

// Returns minimum number of
// jumps to reach arr[h] from arr[l]
int minJumps(int arr[], int l, int h)

这很清楚。

实现递归函数时的任务是将问题分解为一个或多个基本情况，以及通过递归调用解决一个或多个较小问题的递归步骤，然后使用结果解决整个问题。

这里的基本情况是在同一位置开始和结束。不需要任何步骤。返回0。

（作者还将零数组元素视为特例。那是不必要的。如果这些行被删除，程序将同样工作。）

递归步骤实现了这一思想：

要从l到h，首先从l到i迈出一步，然后（递归）计算出从i到h的最小步数S。因此，步骤总数为s1。

为i选择什么？找到最少步数的唯一方法是考虑所有的可能性并取最小值。这些可能性是<代码> L 1 < /代码>通过<代码> h <代码>，即一开始的长度为1的初始步骤，在一步内将整个间隙从<代码> L<代码>代码> <代码> h >代码（因此第二步长度为零）。