如何将尾递归函数转换为迭代函数

h4kerlinguist

如何转换以下函数以使其具有迭代性？

public static int recursion(int x, int y) {
    if(x <= 0) {
        return y + 13;
    } else if (x == 1) {
        return y;
    } else {
        return y * recursion(x - 2, y);
    }
}

梦想崩溃

TL;DR最终代码：

public static int iterative(int x, int y) {
    int result = 1;
    if(x <= 0) return y + 13;
    for(; x >= 0; x -= 2)
        result *= (x <= 0) ? y + 13 : y;
    return result;
}

您的情况的技术是将递归调用转换为循环：

      while(true){

      }

让我们看看递归调用y * recursion(x - 2, y);有一个乘法并且只有x变化，所以我们需要创建一个变量来跟踪乘法：

    int result = 1;
    while(true){
      //...
      result *= y;
      x = x - 2;
    }

我们初始化为 1，因为它是一个乘法。让我们看看递归调用停止的情况：

   if(x <= 0) {
        return y + 13;
    } else if (x == 1) {
        return y;

让我们将它们添加到循环中：

    int result = 1;
    while(true){
        if(x <= 0) {
            result *= y + 13;
            break;
        }
       else if (x == 1){
            result *= y;
            break;
        }
       result *= y;
       x = x - 2;
    }

现在让我们简化代码，result *= y;显示两次，我们可以将循环改为：

   while(true){
        if(x <= 0) {
            result *= y + 13;
            break;
        }
        result *= y;
        if (x == 1){
            break;
        }
        x = x - 2;
    }

由于的值x在循环外无关紧要，我们可以进一步简化循环：

do{
    if(x <= 0) {
        result *= y + 13;
    }
    else
        result *= y;
    x = x - 2;
}while(x >= 0);

让我们使用三元运算符：

    do{
        result *= (x <= 0) ? y + 13 : y;
        x = x - 2;
    }while(x >= 0);

让我们改用for循环：

public static int iterative(int x, int y) {
    int result = 1;
    for(; x >= 0; x -= 2)
        result *= (x <= 0) ? y + 13 : y;
    return result;
}

我们需要覆盖调用方法时 x <= 0 的情况：

public static int iterative(int x, int y) {
    if(x <= 0) return y + 13;
    int result = 1;
    for(; x >= 0; x -= 2)
        result *= (x <= 0) ? y + 13 : y;
    return result;
}

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。