Question

java编程问题，如何将递归法（recursion）转换成迭代法(iterative)

定义如下，T(0) = 0, T(1) = 1, T(2) = 1, T(3) = 3,
T(n) = T(T(n - 1) - 1) + T(n - T(n - 1)); 当 n > 3: 用java递归法与迭代法分别写出程序求出T（20）
本人已经写出递归法如下：
import java.util.*;
public class T
{
public static void main(String[] parms)
{
process();
System.out.println("All done!");

}
public static void process()
{

int t;
int n;
long start, stop, elapsedTime;

n = 20;
start = System.nanoTime();

heyaNum = countHeya(n);

stop = System.nanoTime();
elapsedTime = stop - start;

System.out.println(t);
System.out.println("The elapsedTime is:"+ elapsedTime);

System.out.println("End of processing");

}

public static int countT(int n)
{
int t;

if(n==0)
{
t = 0;;
}
else if(n==1)
{
t = 1;
}
else if(n==2)
{
t = 1;
}
else if(n==3)
{
t = 3;
}
else
{
t = countT(countT(n-1)-1)+countT(n-countT(n-1));
}

return t;
}
}

高手们，如何讲以上程序变成迭代法，用循环结构的

Answer 1

所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以顺推或倒推的方法来完成
现在已知T(0) = 0, T(1) = 1, T(2) = 1, T(3) = 3
及T(n) = T(T(n - 1) - 1) + T(n - T(n - 1)); 当 n > 3:
你就可以从前往后推
比如像这样：
int a[100]={0,1,1,3};
while(n>3 && n<total)//total就是你需要求的最后一个数的下标
{
a[n] = a[a[n - 1] - 1] + a[n - a[n - 1]];
n++;
}
当然我这是简单写一下，你还要考虑是否越界什么的。