折纸问题（递归求解）

折纸问题（递归求解）

折纸问题：

请把一段纸条竖着放在桌子上，然后从纸条的下边向上方对折1次，压出折痕后展开。

此时 折痕是凹下去的，即折痕突起的方向指向纸条的背面。如果从纸条的下边向上方连续对折

2 次，压出折痕后展开，此时有三条折痕，从上到下依次是下折痕、下折痕和上折痕。

给定一 个输入参数N，代表纸条都从下边向上方连续对折N次，请从上到下打印所有折痕的方向。

例如：N=1时，打印： down；N=2时，打印： down down up

思路：通过总结规律的当折了n次时，折痕顺序是是n层的二叉树中序遍历顺序

借助中序的递归输出即可，但是递归需要思考几个问题：

递归过程是什么？终止条件是什么？返回值是什么？完成这些需要什么参数，这些参数可以当作入口参宿和传递进来
类似递归改进问题可见：求解完全二叉树的结点个数

在此输出顺序是down up 所以在输出时要判断down还是up 显然左结点是down 右结点是up  即可以在递归传入左右节点的时候代入参数值 down或者up ，另外递归的终止条件，显然是递归到第N层，完成输出 因此需要一个参数记录当前层数 以及折纸次数N

public class paperFold {public static void paper(int N) {printpaper(N,1,true);}public static void printpaper(int N,int i,boolean down) {if(i>N) return;printpaper( N, i+1,true);if(down) System.out.println("down");else System.out.println("up");printpaper(N,i+1, false);	}public static void main(String[] args) {int N = 4;paper(N);}}

更多类似改递归求解问题比如 求完全二叉树结点个数