后端 递归

temoo · March 17, 2020 · 8 hits

  • 什么是递归?

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

No Reply at the moment.
You need to Sign in before reply, if you don't have an account, please Sign up first.