Recursive는 크게 return하는 구조와 return하지 않는 구조로 나눌 수 있다.

return 없는 구조는 단순히 외부 array에 추가하면 되서 쉽지만 return이 있는 구조는 어려워 한다.

[참고하면 좋은 링크]

https://leetcode.com/problems/permutations/discuss/18284/Backtrack-Summary:-General-Solution-for-10-Questionsh

[RETURN 없는 구조]

재귀 구조로 다시 끌어 올라갈 때 자식의 값이 위에서 필요없는 경우에 다 Return이 없다. 난이도가 쉬운 편. 보통 BackTracking구조라고 보면 됨

• 전체 끝까지 순회해서 전체 PATH를 구해야하는 상황
• 순회하면서 특정 노드의 값을 배열에 담아야하는 상황

[Return 있는 구조]

결국 자식의 값으로 부터 뭔가를 처리해야 한다면 전부 Return이 있는 구조다. 부분문제를 잘 정의해야 한다. 경계 값에만 return 해주는 것이 아니라, 마지막에 부분해를 이용해 계산된 결과를 또 Return 해야 한다.

• 최상위 노드에서 최대, 최솟값을 구해야하는 경우

자식 노드로 부터 return된 결과들 중 max로 최댓값을 구한다. 그리고 이를 Return 한다. 자식이 2개이면 두 값을 받아온 후 이 중에서 max 혹은 min 값을 적용한 후 이를 return 하면 된다. 만약 복수 개이면 반복문을 돌려서 이 중에서 max, min값을 구한 후 return하면 된다.

• DP를 사용하는 경우

https://leetcode.com/problems/find-largest-value-in-each-tree-row/