学习递归算法引起的思考

最近突然想研究下递归算法到底是什么运行的，于是写了一下这段代码，debug了不下十次：

1 public static void main(String[] args) { 2 sum(4); 3 } 4 5 public static int sum(int n) { 6 if (n == 1) { 7 return 1; 8 } 9 System.out.println(n); 10 int sumInt = sum(n - 1)*n; 11 System.out.println(sumInt); 12 return sumInt; 13 }

递归算法分为两部分，一部分是递来，一部分是归去；递归必须要有终止条件，不然会无限死循环下去，例如：上述代码的6至8行代码；

递来：

　　循环执行6至9行的代码，直到n=1，终止循环；（4->3->2->1（终止））

归去：

　　循环执行10至12行代码，直到循环结束；（2->3->4）

--------------------------------------------------------------------------------------------------------------------

原理也可以理解成入栈跟出栈：

入栈：

先从4->3->2->1（终止），得到sum(1)=1;

出栈：

2->3->4

可以得到：

　　sum(2) = sum(n-1) * n = sum(1) * 2 = 1 * 2 = 2;

　　sum(3) = sum(n-1) * n = sum(2) * 3 = 2 * 3 = 6;

　　sum(4) = sum(n-1) * n = sum(3) * 4 = 6 * 4 = 24;

 

可以画图来表示下：

 

 

各位大佬，纯属个人理解，请勿喷，如有问题，麻烦请指出，非常感谢！