6 Recursive Pattern

[출처]

6 Patterns

• Each pattern provides a basic framework
• one you understand the framework, you can fit all problems into one of these frameworks
• these patterns overlap extensively - find the pattern that works for you
• all patterns are based on basic recursive principles

---

Index

1. Iteration
2. Breaking into Subproblems
3. selection
4. ordering
5. divide and conquer
6. depth-first search 

---

Iteration

• iterate over array/list using recursion
• rarely useful except for simplifying code
• Examples
  • print a linked list in reverse order
  • factorial
  • any time when you might use a for loop

//Recursively
func printReversedLinkedList(_ head : Node?) {
	guard let node = head else{
    	return
    }
    printReversedLinkedList(node.next)
    print(head)
}

//Iteratively
func printReversedLinkedList(_ head : Node?) {
	var stack : [Node] = []
    while head != nil {
    	stack.push(head)
        head = head.next
    }
    while !s.isEmpty {
    	print(s.removeLast())
    }
}

---

Breaking into Subproblems

• Classic recursive problems
• Technically all recursive problem, but many are not obvious (hence other pattern)
• use this pattern when it makes sense to you
• Examples
  • Towers of Hanoi
  • Fibonacci

---

Selection (Combinations)

• Fundamentally, problems that can be solved by finding all valid combinations
• Brute force - find and validate every combination
• Optimize by validating as we go/backtracking
• Examples
  • Knapsack problem
  • Word break
  • phonespell
  • N Queens
• can be optimized by DP

---

Ordering (permutations)

• similar to selection except order matters
• brute force - find all permutations and validate which is best/matches our conditions
• Examples
  • Find all Permutations of inputs
  • Find all N-digit numbers whose digits sum to a specific value
  • word squares

---

Divide and Conquer

subproblem is kind of size of one for solution to solve whole problem
but Divide and Conquer is like size of half and using result for solve whole problem

• Can we solve the problem for each half of the input and easily combine the result
• common with searching, sorting, trees
• Examples
  • MergeSort
  • generate all BSTs for a set of items
  • Find all valid parentheses

---

Depth First Search

• Common technique with tree/graph structures
• Can be used for many different recursive problems
• Examples
  • Search in tree
  • Probability of knight on a chessboard
  • many recursive problem if framed properly

---