如何将递归转换为循环

简书 賈小強
转载请注明原创出处，谢谢！

动机

1，递归效率没有循环高，有额外的方法调用开销
2，堆栈溢出（stackoverflow）
3，递归有时挺难理解（不过很多算法用递归最容易实现）

直接法

1， 首先找到递归的结束条件，并且每次递归调用肯定是逼近结束条件（Base Case）
2， 实现一个相同结束条件的循环，每次循环逼近结束条件

public class CountDown {
    public void countDown(int n) {
        if(n == 0) return;

        System.out.println(n + "...");
        waitASecond();
        countDown(n-1);
    }

    public void waitASecond() {
        try {
            Thread.sleep(1000);
        }
        catch (InterruptedException ignore) {
        }
    }

    public static void main(String[] args) {
        CountDown c = new CountDown();
        c.countDown(10);
    }
}

重构后

public class CountDown {
    public void countDown(int n) {
        while(n > 0) {
            System.out.println(n + "...");
            waitASecond ();
            n -= 1;
        }

    }

    public void waitASecond() {
        try {
            Thread.sleep(1000);
        }
        catch (InterruptedException ignore) {
        }
    }

    public static void main(String[] args) {
        CountDown c = new CountDown();
        c.countDown(10);
    }

显式栈法

通过显示定义的栈模拟系统方法栈，将每个方法的局部变量存入自定义栈中，然后再循环

package com.lab0.test2;

public class TestFactorial1 {
    public static int factorial(int n) {
        if (n == 0)
            return 1;
        else
            return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(3));
    }
}

转换后

package com.lab0.test2;

import com.lab1.test1.LinkedStack;

public class TestFactorial2 {
    public static void main(String[] args) {
        LinkedStack<Integer> stack = new LinkedStack<>();
        for (int i = 3; i > 0; i--) {
            stack.push(i);
        }
        int result = 1;
        for (int v : stack) {
            result *= v;
        }
        System.out.println(result);
    }
}

Happy learning !!