Zoe Ding's Blog

递归程序转非递归

(本栏目叫做“小白学编程”，也就是我作为小白记录一些遇到的编程问题，请各位大神多多指教和轻喷哈...)

这个周遇到一道Java作业题，一开始绞尽脑汁没有思路。题目是这样的：

Write a method int thisIsIterative(int n) which is defined as follows (you cannot use recursion):

简单描述一下就是：现在需要写一个 method 叫做 thisIsIterative(int n)，当 n<0 时返回 -10，当 n==0 时返回 2，当 n==1 时返回 5，其他情况返回 thisIsIterative(n-1) + 3 * thisIsIterative(n-2) + 2 * n。当然如果只是有如上条件就太简单了，但是题目限制我们不能用递归（Recursion）做。

一开始一直在用迭代（Iteration）想，发现根本做不出来，后来问了一下一个同学，她的方法是用 array 来存每个 n 的值。这样是跑的通的，但是可能只对 n 数值小的情况下比较好做，如果 n 太大就需要不断扩大数组。然后想到用 stack，把先把两个数 push 进 stack，然后计算第三个数的时候再把前两个 pop 出来，这样stack里始终只存有两个数。

下面是我自己写的代码，还不知道对不对..

public int thisIsIterative(int n){
     Stack<Integer> stack = new Stack<Integer>();
     if (n < 0) {
         return -10;
     } else {
         for (int i = 0; i <= n; i++) {
             if (i == 0) {
                 stack.push(2);
             } else if (i == 1) {
                 stack.push(5);
             } else {
                 int tmp1 = stack.pop();
                 int tmp2 = stack.pop();
                 int tmp = tmp1 + 3 * tmp2 + 2 * i;
                 stack.push(tmp1);
                 stack.push(tmp);
             }
         }
     }
     return stack.pop();
}

总结一下：递归和非递归的区别是，递归是从现在的值开始倒推，是函数调用自身，写起来比较简单，但是据说有一系列问题；而非递归就是正常的从起始开始算，递归转非递归可以用stack来做。很多问题用递归和非递归都可以解决，比较典型的问题是二叉树，用两种方法都能实现遍历。