Converting an iterativ function to a recursive one-CodePudding

Can anybody convert this iterative function to a recursive one? thanks

int b = 1; //what should be converted from
for(int i=0;i<=k;i  ){
  b=b 1 b;  
}

tried this, but got an integer overflow, so I'm obviously doing something wrong

public static int o(int k){ //recursive try
  if(k<0) return -1;
  else{
    if(k==0) return 1;
    else return o(k 1 k);  
  }  
}

Can anybody convert this iterative function to a recursive one? thanks

CodePudding user response：

Here's an example showing you the "stack trace" in both the iterative and recursive versions:

  public static void main(String[] args) {
    int k = 7;

    int b = 1;
    System.out.println("Starting Conditons:");
    System.out.println("b: "   b   ", k: "   k);
    System.out.println("Iterative trace:");
    for(int i=0;i<=k;i  ){      
      b=b 1 b;  
      System.out.println("i: "   i   ", b: "   b);
    }
    System.out.println("Iterative: b = "   b);

    b = 1;
    System.out.println();
    System.out.println("Starting Conditons:");
    System.out.println("b: "   b   ", k: "   k);
    System.out.println("Recursive trace:");    
    b = foo(0, k, b);
    System.out.println("Recursive: b = "   b);
  }

  public static int foo(int i, int k, int b) {    
    System.out.println("i: "   i   ", b: "   b);
    if (i > k) {
      return b;
    }
    else {      
      return foo(i 1, k, b 1 b);
    }
  }

Output:

Starting Conditons:
b: 1, k: 7
Iterative trace:
i: 0, b: 3
i: 1, b: 7
i: 2, b: 15
i: 3, b: 31
i: 4, b: 63
i: 5, b: 127
i: 6, b: 255
i: 7, b: 511
Iterative: b = 511

Starting Conditons:
b: 1, k: 7
Recursive trace:
i: 0, b: 1
i: 1, b: 3
i: 2, b: 7
i: 3, b: 15
i: 4, b: 31
i: 5, b: 63
i: 6, b: 127
i: 7, b: 255
i: 8, b: 511
Recursive: b = 511