编程的角度来看,程序调用自身的编程技巧称为递归(recursion)。 本质上将原来的问题转化成更小的同一问题。就是一个函数直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
1、边界条件 2、递归前进段 3、递归返回段 当边界条件不满足时,递归前进;当边界条件满足时,递归返回。
public static int getFactorial(int n) {
int temp = 1;
if (n >= 0) {
for (int i = 1; i <= n; i++) {
temp = temp * i;
}
} else {
return -1;
}
return temp;
}
递归表示
public static int getFactorial(int n) {
if (n==0){
System.out.println(n + "!=1");
return 1;
}
if (n>0){
System.out.println(n);
int temp = n*getFactorial(n-1);
System.out.println(n + "!=" + temp);
return temp;
}
return -1;
}
n相加递归表达
public static int getFactorial(int n) {
if (n==0){
return 0;
}
return n+getFactorial(n-1);
}
递归的过程就是出入栈的过程
image
第 1~4 步,都是入栈过程,Factorial(3)
调用了Factorial(2)
,Factorial(2)
又接着调用Factorial(1)
,直到Factorial(0)
;
第 5 步,因 0 是递归结束条件,故不再入栈,此时栈高度为 4,即为我们平时所说的递归深度;
第 6~9 步,Factorial(0)
做完,出栈,而Factorial(0)
做完意味着Factorial(1)
也做完,同样进行出栈,重复下去,直到所有的都出栈完毕,递归结束。
每一个递归程序都可以把它改写为非递归版本。我们只需利用栈,通过入栈和出栈两个操作就可以模拟递归的过程,二叉树的遍历无疑是这方面的代表。
但是并不是每个递归程序都是那么容易被改写为非递归的。某些递归程序比较复杂,其入栈和出栈非常繁琐,给编码带来了很大难度,而且易读性极差,所以条件允许的情况下,推荐使用递归。
image
问题描述为:有三根杆子 A,B,C。A 杆上有 N 个穿孔圆盘,盘的尺寸由上到下依次变大,B,C 杆为空。要求按下列规则将所有圆盘移至 C 杆:
void Hanoi(int n, char a, char b, char c){ //终止条件
if (n == 1)
{
cout << a << "-->" << c << endl;
return;
} //通用情况
Hanoi(n - 1, a, c, b);
Hanoi(1, a, b, c);
Hanoi(n - 1, b, a, c);
}
image
首先看下基本情况,即终止条件:当为空树时,节点数为 0; 再来看下通用情况:当前节点的左,右子树节点数都被求出,则以当前结点为根的二叉树的节点总数就是 “左子树 + 右子树 + 1”。
代码如下:
int GetNodes(Node * node){ //终止条件
if (node == nullptr)
return 0; //通用情况
return GetNodes(node->left) + GetNode(node->right) + 1;
}