[Programming] Recursive

• Programming problems 中重要的一個分類就是 recursive
• e.g. 著名的 n 階算法
int factorial(int n) { if (1 == n) return 1; if (0 == n) return 1; return n * factorial(n-1); }
• 但更重要的是應該要考慮 recursive 的限制
• stack overflow
• 解法: 
• tail recursive
• 連結內的解釋相當清楚, 主要是透過寫法不同, 讓 compiler 在 O2, O3的 optimization時, 不用 call function, 而是 jne (jump not equal)

• int factorial_acc(int n, int acc = 1) 
  {    
      if (n == 1) 
          return acc;
      else
          return factorial_acc(n - 1, n * acc);
  }
  

• iterative

• int factorial_iterative(int n)
  {
      int acc = 1;
      if (n <= 1) return acc;
      while (n > 1)
      {
          acc *= n;
          n--;
      }
      return sum;
  }

• 延伸閱讀
• Iterative vs. Recursive
• Stack size
• stack vs heap