什么是递归?
我怎么知道!偷偷 Google 下,结果笑哭。。
言归正传,递归就是对象调用自己。递归算法包含:递归出口 + 递归公式
尾递归:如果一个递归过程或递归函数中递归调用语句是最后一条执行语句,则称这种递归调用为尾递归。
比如下面阶乘代码实现就是尾递归
int fac(int n)
{
if (n==0||n==1)
return 1;
else
return n * fac(n-1);
}
例题
汉诺塔问题
/*
#思路:
将n个盘分为前‘n-1’和最后一个两部分,如果只有一个盘直接移动到‘z’即可,
否则,先将前‘n-1’这部分从‘x’通过‘z’移到到‘y’,再将最后一个直接从‘x’->‘z’
最后将前‘n-1’从‘y’->‘x’->‘z’
*/
public static int hanoil(int n,char x,char y,char z) {
if (n == 1) // 只有一个盘子时,将其从X塔移动到Z塔
System.out.println(x+"->"+z);
else {
//借助Z塔,将前n-1个盘子从X塔移动到Y塔
hanoil(n-1,x,z,y);
//将X塔上剩下的1个盘子移到Z塔
System.out.println(x+"->"+z);
//借助X塔,将前n-1个盘子从Y塔移动到Z塔
hanoil(n-1, y, x, z);
}
return (int) (Math.pow(2, n)-1);//移动总步数
}
反转二叉树
TreeNode* invertTree(TreeNode* root) {
if(root == NULL)
return NULL;
TreeNode* item = root->left;
root->left = root->right;
root->right = item;
invertTree(root->left);
invertTree(root->right);
return root;
}
/*
递归版本稍微复杂一些,关键是向后退。假设列表的其余部分已经被颠倒了,现在如何扭转前面部分?
我们假设列表是:n 1 →...→n k-1 →n k →n k + 1 →...→n m →Ø
从节点n k + 1到n m的假设已经被反转,并且在节点n k处。
n 1 →...→n k-1 → n k →n k + 1 ←...←n m
我们希望n k + 1的下一个节点指向n k。
所以,n k .next.next = n k ;
要小心,n 1的下一个必须指向Ø。如果您忘记了这一点,您的链接列表就会有一个循环。
*/
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode p = reverseList(head.next);
head.next.next = head;
head.next = null;
return p;
}
递归算法到非递归算法的转换
递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的;然而,递归算法的时间效率通常比较差。因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。
转换方法
对于尾递归和单向递归的算法,可用循环结构的算法替代;
比如斐波那契问题:
//先来看看递归算法
int fibonacci(int n) {
if(n==1)
return 0;
if(n==2)
return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
//将其转换为非递归算法
int fibonacci(int n) {
if(n==1)
return 0;
if(n==2)
return 1;
int a=0,b=1,c=0;
for (int i = 3; i <= n; ++i)
{
c = a + b;
a = b;
b = c;
}
return c;
}
利用栈(其实递归本身就是栈的应用)
进制转换(十进制->其他进制):
//利用递归实现
void Convert(int num, int d)
{
char ch[] = "0123456789ABCDEF"; //进制所使用的数字
if(num == 0)
cout<<"结果: ";
else{
Convert(num/d,d);
cout<< ch[num % d];
}
}
//利用栈实现
void Convert(int num, int d)
{
//num为待转换数,d为进制
SqStack S;
ElemType result;
int r; //余数
char ch[] = "0123456789ABCDEF"; //进制所使用的数字
InitStack(S);
while (num != 0) {
r = num%d; //取余数r
Push(S, ch[r]); //余数入栈
num = num / d; //利用商进行下一次运算
}
while (StackEmpty(S) != 1) {
Pop(S, result);
cout << result-'0';
}
}