递归

​

• 什么是递归？

  我怎么知道！偷偷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;
    }
    

  • 206. Reverse Linked List

    /*
    递归版本稍微复杂一些，关键是向后退。假设列表的其余部分已经被颠倒了，现在如何扭转前面部分？
    我们假设列表是：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';
    	}
    }
    

    ​