How to convert tail-recursive function to iterative

Question

How can you convert the following function so that it is iterative?

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

TL;DR Final code:

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

---

The technique in your case is to turn the recursive call into a loop:

      while(true){

      }

let us look at the recursive call y * recursion(x - 2, y); there is a multiplication and only x changes, so we need to create a variable to keep track of the multiplication:

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

We initialized to 1 because it is a multiplication. Let us look at the cases where the recursive call stops:

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

let us add them into loop:

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

Now let us simplify the code, result *= y; shows two times, we can change the loop into:

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

Since the value of x does not matter outside the loop we can simplify the loop even further:

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

Let us use the ternary operator:

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

Let us use a for loop instead :

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

We need to cover the case when the method is called with 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;
}