Home / Questions / 29735
Accepted
RoyalUp
Asked: 2020-10-26 08:40:22 +0800 CST 2020-10-26 08:40:22 +0800 CST

Recursive to iterative with bottom-up

  • 772

This is my code for a recursive function written in non-final form, I would like to make it iterative with a while , but I really can't do it, advice to do it with bottom-up? The abc method is a square root(x) , and the number of iterations performed (n) , the higher the iteration the better the result.

public static Double abc(int x,int n){
    Double d = .0;
    if(n==0){ //caso base
        d = 1.0;
    }else{
        d = (abc(x,n-1)+(x/abc(x,n-1)))/2;
    }
    return d;
}

This is what I have tried with the while loop:

  public static Double abcIter(Integer x,Integer n){                 
    Double res = 1.0;
    Double r0=.0;
    Integer numeroAuxiliar = 0;

        while(numeroAuxiliar<=n){

            res = (res+(x/res))/2;
            r0 = res;
            res = (r0+(x/r0))/2;
            numeroAuxiliar++;
        }


    return res;
}

When I try some root and iteration with the while it doesn't give me the exact value. On the other hand, the first method works well for me. Tips on the while method, and bottom-up?

java

2 Answers

  1. Best Answer

    Any recursive function with tail recursion can be made into an iterative function.
    A tail recursive function is one that always ends in return metodoRecursivo(parametros)or return expresion_sin_llamada_recursiva.

    Your function is not tail recursive but can be converted to tail recursive by passing an accumulator parameter (this is the hardest step):

    public static Double abc(int x,int n){
  return abcRecurs(x, n, 1.0);
}  

public static double abcRecurs( int x, int n, double acc ) {
    if(n==0){ 
        return acc;
    }else{
        return abcRecurs( x, n-1,  (acc+x/acc)/2 );
    }
}

    Once we have the function in tail recursive form, the steps are always the same and are done mechanically.
    First put a loop while (true)around the function:

    public static double abcRecurs(int x, int n, double acc) {
  while (true) {
    if (n == 0) {
      return acc;
    } else {
      return abcRecurs(x, n - 1, (acc + x / acc) / 2);
    }
  }
}

    Second, change all recursive calls abcRecurs( /*parm a*/ a1, /* parm b*/ b1, etc )to :a=a1; b=b1; etc; continue;

    public static double abcRecurs(int x, int n, double acc) {
  while (true) {
    if (n == 0) {
      return acc;
    } else {
      x = x;
      n = n - 1;
      acc = (acc + x / acc) / 2;
      continue;
    }
  }
}

    And now you have your iterative function. To finish you can clean it a little. For example x=x;, it is useless.

    public static double abcRecurs(int x, int n, double acc) {
  while ( n>0 ) {
    --n;
    acc = (acc + x / acc) / 2;
  }
  return acc;
}

    And after this you can combine abc and abcRecurs into one :

    public static Double abc(int x, int n) {
  double acc = 1.0;
  while (n > 0) {
    --n;
    acc = (acc + x / acc) / 2;
  }
  return acc;
}
    • 5

  2. Try this.

    public static Double abcIter(Integer x, Integer n) {
    Double res = 1.0;
    Integer numeroAuxiliar = n;

    while (numeroAuxiliar !=0) {
        res = (res + (x / res)) / 2;
        numeroAuxiliar--;
    }

    return res;
}
    • 2