递归转迭代

两种类型

• 尾递归：直接转就行

AcWing 717. 简单斐波那契
二叉树的前序遍历

// 例子：斐波那契数列
// 尾递归形式
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        dfs(0, 1, 1, n);
    }
    static void dfs(int a, int b, int u, int n) {
        if (u > n) return;
        if (u == 1) {
            System.out.print(a + " ");
            dfs(a, b, u + 1, n);
        } else if (u == 2) {
            System.out.print(b + " ");
            dfs(a, b, u + 1, n);
        } else {
            System.out.print(a + b + " ");
            int t = a + b;
            a = b;
            b = t;
            dfs(a, b, u + 1, n);
        }
    }
}

// 迭代写法
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a = 0, b = 1;
        for (int i = 1; i <= n; i++) {
            if (i == 1) {
                System.out.print(a + " ");
            } else if (i == 2) {
                System.out.print(b + " ");
            } else {
                int t = a + b;
                System.out.print(t + " ");
                a = b;
                b = t;
            }
        }
    }
}

• 普通递归

使用栈维护

1. 参数
2. 局部变量
3. 返回位置

Acwing 93. 递归实现组合型枚举

// 递归写法
import java.util.*;
public class Main {
    static int n, m;
    static int[] res = new int[30];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        dfs(1, 1);
    }
    static void dfs(int u, int start) {
        if (u == m + 1) {
            for (int i = 1; i <= m; i++)
                System.out.print(res[i] + " ");
            System.out.println();
            return;
        }
        for(int i = start; i + m - u <= n; i++) {
            res[u] = i;
            dfs(u + 1, i + 1);
        }
    }
}

// 迭代写法
import java.util.*;
public class Main {
    static int n, m;
    static int[] res = new int[30];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Deque<State> stk = new LinkedList<>();
        stk.offer(new State(0, 1, 1));
        while (!stk.isEmpty()) {
            State t = stk.pop();
            if (t.pos == 0) {
                if (t.u == m + 1) {
                    for (int i = 1; i <= m; i++)
                        System.out.print(res[i] + " ");
                    System.out.println();
                    continue;
                }
                if (t.start + m - t.u <= n) {
                    res[t.u] = t.start;
                    t.pos++; t.start++;
                    stk.push(t);
                    stk.push(new State(0, t.u + 1, t.start));
                }
            } else if (t.pos == 1) {
                if (t.start + m - t.u <= n) {
                    res[t.u] = t.start;
                    t.start++;
                    stk.push(t);
                    stk.push(new State(0, t.u + 1, t.start));
                }
            }
        }
    }
}
class State {
    int pos, u, start;
    State(int pos, int u, int start) {
        this.pos = pos;
        this.u = u;
        this.start = start;
    }
}

其它：

• 二叉树的中序/后序遍历