Recursive to iterative with bottom-up

Question

Recursive to iterative with bottom-up

Navigation

#1 by (5 votes)
#2 by (2 votes)

2

This is my code of a recursive function written in an non-final form, I would like to pass it to iterative with a while, but I really can not 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 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 does not give me the exact value. On the other hand, the first method if that works for me. Advice on the while method, and bottom-up?

java

asked by RoyalUp 25.10.2016 в 18:40

source

2 answers

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

answered by 25.10.2016 в 20:26

noo I can declare the global variable How to achieve the YouTube page load effect?

score 5 · Accepted Answer

All recursive functions with recursion of queue can be converted into an iterative function.
A function with tail recursion is one that always ends in return metodoRecursivo(parametros) or in return expresion_sin_llamada_recursiva .

Your function is not recursive queue but can be converted to queue recursive by entering an accumulator parameter (this is the most difficult 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 recursive tail 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 ) by: 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 you already have your iterative function. To finish you can clean it a little. For example x=x; 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 that you can combine abc and abcRecurs in one:

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