怎么优化该递归？

Question

递归优化

Answer 1

把 int m,n;提出来。import java.util.Scanner;public class Main {
public static int depth(int m,int n){
if(m==n)
return 1;
else if(m>n)
return 0;
else
return depth(m*2,n)+depth(m*2+1,n)+1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
                                       int m,n;
while(true)
{

m=sc.nextInt();
n=sc.nextInt();
if(m==0&&n==0)
break;
else
{
System.out.println(depth(m,n));
}
}
sc.close();
}
}

Answer 2

public class T {

public static void main(String[] args) {
int m = 2;
int n = 999999999;

int ml = level(m);
int nl = level(n);

if(ml == nl) {
System.out.println(1);
return;
}

int ct = 0;
int lct = 1;
for(int i = ml; i < nl; i++) {
ct += lct;
lct *= 2;
}


int ms = getS(m, nl - ml);
int me = getE(m, nl - ml);
for(int i = getS(1, nl - 1); i <= n; i++) {
if(i >= ms && i <= me) {
ct++;
}
}

System.out.println(ct);
}

public static int getS(int a, int b) {
for(int i = 0; i < b; i++) {
a *= 2;
}

return a;
}

public static int getE(int a, int b) {
for(int i = 0; i < b; i++) {
a *= 2;
a++;
}

return a;
}

public static int level(int i) {
if(i == 1) {
return 1;
}
if(i % 2 == 0) {
return level(i / 2) + 1;
}
return level((i - 1) / 2) + 1;
}
}

Answer 3

import java.util.Scanner;public class Test {
public static int[] res = new int[1000000]; 
public static void init(){
for(int i=0;i<1000000;i++){
res[i] = 0;
}
}
    public static int depth(int m,int n){
if(res[m]>0) return res[m];
        if(m==n)
            return 1;
        else if(m>n)
            return 0;
        else
            return res[m] = depth(m*2,n) + depth(m*2+1,n)+1;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(true)
        {
            int m,n;
            m=sc.nextInt();
            n=sc.nextInt();
            if(m==0&&n==0)
                break;
            else
            {
init();
                System.out.println(depth(m,n));
            }
        }
        sc.close();
    }
}
这个题目，如果测试数据严格的话，即m取极小，n取极大，用int可能会溢出，那样的话，这里定义的res[]数组也不能满足要求。