Java中递归的如果想要达到C++的传参效果的一种写法
常识：
我们都知道 Java方法的参数传递是值传递，就是说如果参数是基本数据类型，那么直接拷贝一份副本给形参，如果参数是对象，不是基本数据类型，那么拷贝对象的引用的副本，也就是相等于是拷贝了一份指向这个对象指针，这样在方法中通过形参修改对象的属性或者字段，是会对原来的对象产生影响的，因为本质上这两个是同一个对象。
问题：
C++里面的值传递是在形参中拷贝一份对象的副本，而Java中没有这种传递方式，Java中的值传递类似于C++里面的引用传递。所以C++的递归在不同深度的递归中形参中的对象是不会相互影响的，所以C++天生就帮我们做了递归层次之间的参数隔离，但是Java 会有这个问题，Java方法中的参数传递不会重新创建对象，而是引用的同一个对象，所以后面更深层次的递归就会对回溯后的形参对象产生影响。
我考虑的是怎么消除这种影响，达到和C++一样的效果。
比如图中代码中的这个函数形参中的两个对象，一个栈，和一个列表，我怎么样可以让更深次的修改不会对回溯后的本层次造成影响呢，
我的方式是：既然这两个对象在每个层次的递归都是一样的，都是这两个对象，那么这两个对象定义成局部变量就没有什么用了，所以干脆定义成全局变量，但是在每次在本层次递归进行后，都必须进行回溯，消除递归的影响，改动后的代码如下：
我们以往的递归往往是不会在最后一个选择后进行消除回溯的，因为这没什么用，但是这里需要回溯。
这个代码完整的问题如下：
栈是一种重要的数据结构，其主要的操作包括入栈和出栈。请编写程序，对任意给定的n，输出 1，2，…，n 的所有出栈顺序。
输入：正整数 n（1≤n≤9）
输出：输出 1，2，…，n 的所有出栈顺序
例如：
用递归的思路进行解题：每次进入递归都判断这次是入栈还是出栈
C++式写法：
1 // 栈是一种重要的数据结构，其主要的操作包括入栈和出栈。请编写程序，对任意给定的n，输出 1，2，…，n 的所有出栈顺序。 2 #define _CRT_SECURE_NO_WARNINGS 3 #include <stdio.h> 4 #include <stack> 5 #include <vector> 6 using namespace std; 7 8 int n; 9 vector<vector<int>> v; 10 11 void dfs(int i, stack<int> S, vector<int>& temp) 12 { 13 // 每次进入dfs， 判断是否大于等于n, 如果大于n，存储数据，返回 14 if (i > n && S.empty()){ 15 v.push_back(temp); 16 return; 17 } 18 19 // 选择入栈当前元素还是出栈栈顶元素 20 // 选择入栈当前元素 21 if (i <= n) 22 { 23 S.push(i); 24 dfs(i + 1, S, temp); 25 S.pop(); // 消除入栈的影响 26 } 27 28 // 选择出栈当前元素 29 if (!S.empty()) 30 { 31 temp.push_back(S.top()); 32 S.pop(); 33 dfs(i, S, temp); 34 temp.pop_back(); 35 } 36 } 37 38 int main() 39 { 40 // 读取数据 41 scanf("%d", &n); 42 // 对这个数据进行dfs递归，求出所有出栈顺序 43 stack<int> S; 44 vector<int> temp; // 存储一个弹出序列 45 dfs(1, S, temp); 46 47 for (int i = 0; i < v.size(); i++){ 48 for (int j = 0; j < v[i].size(); j++) 49 printf("%d ", v[i][j]); 50 printf(" "); 51 } 52 53 return 0; 54 }
我把这个C++代码初步改成Java代码
1 package report2; 2 3 import java.util.ArrayList; 4 import java.util.Scanner; 5 import java.util.Stack; 6 7 // 利用递归打印所有出栈序列 8 public class Solution1_1 { 9 // 存储全排列的数组 10 public static ArrayList<ArrayList<Integer>> ps = 11 new ArrayList<>(); 12 public static int n; 13 14 15 public static void main(String[] args) { 16 // 读取输入 17 Scanner in = new Scanner(System.in); 18 n = in.nextInt(); 19 20 // 对这个数据进行dfs递归，求出所有出栈顺序 21 Stack<Integer> s = new Stack<>(); 22 ArrayList<Integer> tmp = new ArrayList<Integer>(); 23 stackPopPermutation(1, s, tmp); 24 25 // 打印所有的出栈序列 26 for(int i = 0; i < ps.size(); i++){ 27 for(int j = 0; j < ps.get(i).size(); j++){ 28 System.out.print(ps.get(i).get(j) + " "); 29 } 30 System.out.println(); 31 } 32 } 33 34 // tmp参数中存储的是临时的出栈序列 35 private static void stackPopPermutation(int i, Stack<Integer> s, ArrayList<Integer> tmp) { 36 // 每次进入递归，判断 i 是否大于等于n, 如果大于n,存储序列，返回 37 if(i > n && s.empty()){ 38 ps.add(tmp); 39 return; 40 } 41 // 选择入栈当前元素还是出栈栈顶元素 42 // 选择入栈当前元素 43 if (i <= n) 44 { 45 s.push(i); 46 stackPopPermutation(i + 1, s, tmp); 47 s.pop(); // 消除入栈的影响 48 } 49 50 // 选择出栈当前元素 51 if (!s.empty()) 52 { 53 tmp.add(s.peek()); 54 s.pop(); 55 stackPopPermutation(i, s, tmp); 56 // tmp.remove(new Integer(i)); 57 } 58 } 59 }
我同学的代码给我了思路，既然第一次选择后回溯可以使得全局变量回退到刚进入这个函数时的状态，那我第二次选择后再进行一次回溯是不是也可以回退到刚进入这个函数时的状态呢，这样是不是就达到了一种类似于在形参中传递了一个对象的拷贝，而非引用的拷贝呢，因为我们通过手动回溯的方式使得一个全局变量在进入递归到出递归状态没有发生变化，
S、S1、S2均表示一个全局变量的状态
S --> S1 --> 进入递归 --> 出递归 -->回溯 -- > S -- S2 -->进入递归 -- > 出递归 -- > 回溯 -- > S
最终的Java代码：
1 package report2; 2 3 import java.util.*; 4 5 // 利用递归打印所有出栈序列 6 public class Solution1 { 7 8 public static Stack<Integer> s = new Stack<>(); // 一个工作栈 9 public static LinkedList<Integer> tmp = new LinkedList<>(); // 存储一个临时的序列 10 public static int n; 11 12 13 public static void main(String[] args) { 14 // 读取输入 15 Scanner in = new Scanner(System.in); 16 n = in.nextInt(); 17 18 // 对这个数据进行dfs递归，求出并打印所有的出栈序列 19 stackPopPermutation(1); 20 } 21 22 // tmp参数中存储的是临时的出栈序列 23 private static void stackPopPermutation(int i) { 24 // 每次进入递归，判断 i 是否大于等于n, 如果大于n,存储序列，返回 25 if(i > n && s.empty()){ 26 for(int j = 0; j < tmp.size(); j++){ 27 System.out.print(tmp.get(j) + " "); 28 } 29 System.out.println(); 30 return; 31 } 32 33 // 选择入栈当前元素还是出栈栈顶元素 34 // 选择入栈当前元素 35 if (i <= n) 36 { 37 s.push(i); 38 stackPopPermutation(i + 1); 39 s.pop(); // 消除入栈的影响 40 } 41 42 // 选择出栈当前元素 43 if (!s.empty()) 44 { 45 Integer top = s.peek(); 46 tmp.add(top); 47 s.pop(); 48 stackPopPermutation(i); 49 s.push(top); // 消除回溯，消除出栈的影响 50 tmp.removeLast(); 51 } 52 } 53 }