递归计算向非递归计算转换模板

递归计算向非递归计算转换模板
http://www.iteye.com/post/567240
http://www.iteye.com/topic/201241

这一篇实现篇有些误入歧途了。为了通用化而复杂化。
这个问题本身是可以线性化的，不必要树形化。

楼主的代码里面，vlaues (hash map) 保存了所有的中间计算结果，这是没有必要的。这会带来空间的浪费。
楼主的代码本质上是一种查表法（参数值列列表 -> 返回值）。
我们可以简单的用 Method Cache （方法缓存）的方式来实现。
只要用AOP，给这个函数加上Cache缓存（key是 函数名 + 参数列表），就可以轻松实现需要的效果。

第一篇思路篇里面的图很形象。
相当于程序员自己维护一个数组形式的运行栈结构。
在一些支持Continuation的非栈语言中，运行栈其实是树形的运行堆，中间结果都是保留起来的，保留中间结果的这些工作都不需要自己做。
楼主相当于做了一些Continuation的树形运行堆的工作。在栈语言上模拟这种效果，有些事倍功半的感觉。

------------------------------

这类问题其实就是保存前几步中间计算结果的问题。

对于这个问题本身来说
f(x) = f(x-1) + f(x-3)
f(x) = 10 (x < 3)

其实是很简单的，只需要用一个长度为3的数组保存中间结果就可以了。
Java代码 复制代码

    fibonacci(int x){ 
      if(x < 3) 
        return 10; 
     
     
      int[] middleResults = new int[3]{10,10,10}; 
      int result = 0; 
     
      for(int i = 10; i <= x; i++){ 
       result = middleResults[0] + middleResults[2]; 
       move(middleResults); 
       middleResults[0] = result; 
     } 
    
     return result; 
   } 
    
   void move(int[] array){ 
     int k = array.length; 
     int limit = k – 1; 
     for(int i = 0; i < limit; i++){ 
       array[i+1] = array[i]; 
     } 
   } 

fibonacci(int x){
  if(x < 3)
    return 10;


  int[] middleResults = new int[3]{10,10,10};
  int result = 0;

  for(int i = 10; i <= x; i++){
    result = middleResults[0] + middleResults[2];
    move(middleResults);
    middleResults[0] = result;
  }

  return result;
}

void move(int[] array){
  int k = array.length;
  int limit = k – 1;
  for(int i = 0; i < limit; i++){
    array[i+1] = array[i];
  }
}




move 方法主要用来移动中间结果数组里面的中间结果。
其实完全可以用一个 queue 队列来保存中间结果。直接把用过的 queue head 丢弃，把后面的结果加在队尾。正如楼主的代码里面用的queue结构。
只是为了更加形象地表达数组（运行栈）的结构，因此这里用了定长数组。


代码没有调试过，只是一个大概意思。
这段代码是循环形式，也可以写成递归形式，中间结果数组作为参数进行传递。

-------------------------

这个问题本身是Fibonacci问题的变种

Fibonacci问题描述：
1头母牛，出生后第3年，就开始每年生1头母牛，按此规律，第n年时有多少头母牛。
f(1)=1
f(2)=1
f(n)=f(n-1)+f(n-2)

Fibonacci数列：1,1,2,3,5,8,13,,21,34........

Fibonacci问题变种A描述：
1头母牛，出生后第4年，就开始每年生1头母牛，按此规律，第n年时有多少头母牛。
f(1)=1
f(2)=1
f(3)=1
f(n)=f(n-1)+f(n-3)

Fibonacci数列：1, 1, 1, 2, 3, 4, 6, 9,13,19,28........

Fibonacci问题通用描述：
1头母牛，出生后第x年，就开始每年生1头母牛，按此规律，第n年时有多少头母牛。
令k = x - 1
f(1)=1
…
f(k)=1
f(n)=f(n-1)+f(n-k)

-------------------------------------

递归函数：f(x) = ( f(x-1) + f(x-3) + x) / f(x-2), f(x) = 10 (x < 3)
同样可以类似解决。
Java代码 复制代码

   

1. f(double x){ 
2.       if(x < 3) 
3.         return 10; 
4.      
5.      
6.       double[] middleResults = new double[3]{10,10,10}; 
7.       double result = 1; 
8.      
9.       for(int i = 10; i <= x; i++){ 
10.        result = (middleResults[0] + middleResults[2] + i) / middleResult[1]; 
11.        move(middleResults); 
12.        middleResults[0] = result; 
13.      } 
14.     
15.      return result; 
16.    } 
17.     
18.    void move(int[] array){ 
19.      int k = array.length; 
20.      int limit = k – 1; 
21.      for(int i = 0; i < limit; i++){ 
22.        array[i+1] = array[i]; 
23.      } 
24.    }