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

Question

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

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);
    }
}

Answer 1

制作存储所需变量的列表。

一种可能的方法是有两个循环：

在第一个循环中模拟递归调用，并且
在第二个循环中，您然后处理围绕这些调用的公式，即 y*list[i]（伪代码）。

测试： 保留你的递归函数，并编写一个调用两者并比较结果的测试，verify/validate 你的非递归算法。

Answer 2

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

  return result;
}

Answer 3

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

Answer 4

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;
}

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

How to convert tail-recursive function to iterative

java

recursion

iteration

tail-recursion