Unfold Recursion

재귀 전개

 

재귀는 적절하게 사용될 경우 우아하고 직관적인 솔루션이 될 수 있으나

여러가지 이유로 반복 알고리즘으로 변경해야 할 수 있다.

 

• 스택오버플로우의 위험성(Risk of Stackoverflow)
  • 재귀는 종종 시스템 스택에서 추가 메모리 소비를 발생 시키며, 각 프로그램은 제한된 리소스로 운용된다.
  • 이를 피하기 위한 꼬리 재귀가 존재하나 모든 재귀가 꼬리재귀를 사용할 수 있는 것이 아니다
  • 모든 컴파일러에서 꼬리 재귀 최적화를 지원하지는 않는다.
• 능률(Efficiency)
  
  • 중복 계산의 위험성
• 복잡도(Complexity)
  
  • 재귀 남용시 반복 알고리즘 보다 읽고 이해하기가 어려울 수 있다 (중첩된 재귀)

두 TreeNode가 동일한지 비교하는 Solution으로 재귀 -> 반복으로 만들어보자.

 

재귀로 만든 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
  public boolean isSameTree(TreeNode p, TreeNode q) {
    // p and q are both null
    if (p == null && q == null) return true;
    // one of p and q is null
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return isSameTree(p.right, q.right) &&
            isSameTree(p.left, q.left);
  }
}

 

반복문 코드

class Solution {
  public boolean check(TreeNode p, TreeNode q) {
    // p and q are null
    if (p == null && q == null) return true;
    // one of p and q is null
    if (q == null || p == null) return false;
    if (p.val != q.val) return false;
    return true;
  }

  public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (!check(p, q)) return false;
    // init deques
    ArrayDeque<TreeNode> deqP = new ArrayDeque<TreeNode>();
    ArrayDeque<TreeNode> deqQ = new ArrayDeque<TreeNode>();
    deqP.addLast(p);
    deqQ.addLast(q);

    while (!deqP.isEmpty()) {
      p = deqP.removeFirst();
      q = deqQ.removeFirst();

      if (!check(p, q)) return false;
      if (p != null) {
        // in Java nulls are not allowed in Deque
        if (!check(p.left, q.left)) return false;
        if (p.left != null) {
          deqP.addLast(p.left);
          deqQ.addLast(q.left);
        }
        if (!check(p.right, q.right)) return false;
        if (p.right != null) {
          deqP.addLast(p.right);
          deqQ.addLast(q.right);
        }
      }
    }
    return true;
  }
}

ArrayDeque는 Deque(덱/데크)

Double-Ended Queue의 줄임말로 큐의 양쪽으로 엘리먼트의 삽입과 삭제를 수행할 수 있는 자료구조

 

 

다음 두 단계를 수행하여 재귀 접근 방식을 반복 접근 방식으로 변환 할 수 있습니다.

 

1.함수 내에서 Stack 또는 Queue 데이터 구조를 사용하여 시스템 호출 스택의 역할을 대체합니다.

  재귀가 발생할 때마다 재귀를 호출하는 대신 매개 변수를 생성 한 데이터 구조에 새 요소로 푸시하기만 하면됩니다.

 

2. 또한 이전에 생성 한 데이터 구조에 대해 루프를 생성합니다. 

그런 다음 연속된 재귀 호출은 루프 내의 반복으로 대체됩니다.

 

---

Deque 참고 자료

soft.plusblog.co.kr/24

[Java(자바)] Deque(덱/데크) 자료구조