재귀함수에 대한 분석!

재귀함수는 코드를 단순화하기 위해서 사용하는것이다. 마지막 ending condition 하나만 function 앞부분에 지정해두고, 같은 내용의 function 을 argument를 바꾸어서 계속 돌리는 것이다.어떤부분의 code 가 반복된느지 확인하고, 어떤 ending 조건이 있는지 확인해라. dp 의 경우에는 계산식이 3-4가지라서 if 문이 몇개 더들어가긴 하지만..

 

재귀함수는 나를 항상 어렵게 만든다.

DFS DP 모든 재귀함수는 이해하기 어렵고 복잡하다.

그래서 나는 이것을 공식화하고 싶었다. 어떤 어려운 세상문제이던지 파훼법은 있기 때문이다.

 

재귀를 작성할때 헷갈리는 것들이 있다.

 - while 을 써야하는지 IF를 써야하는지,

 - while 을 써야하는지 for 를 써야하는지.

 - return 을 쓸지 말지,  return 으로 무엇을 넘겨줄지

 - 재귀함수로 어떤 인자들을 넘겨줘야하는지

 - 백트래킹은 어떻게 해야할지 , 말단노드에서 어떻게 처리할지

 

연구

 - 재귀함수에서 while을 쓰면 매우 복잡해짐

 - 재귀함수는 보통 while보다는 for / if 안에 들어있음, 또는 아예 밖에 있음

 - 백트레킹 구조 ( return 값이 필요없을때 , 있을떄)

#return 값이 필요없을때
def dfs():
 if 백트래킹체크 ##길이 비교 or 값존재 여부 or depth 등
   지정코드 수행
   return
 
  for / if : 
     dfs()


#########################################3
#return 값이 필요할때
 def dfs():
  if 백트래킹 체크: 
    지정코드 수행
    return null 또는 문제에 따라 적절한 값을 넘겨줌
  for / if :
     a= dfs();
     b= dfs();
    return a,b의 자료형에 맞춰줘야함
    
#########################################
def dfs(...):

	# 탐색 종료 조건
	if 탐색 종료 조건:
        return False
    
  if 추가 탐색 가능 조건:

      # 해당 위치(노드)에 방문했음을 기록하는 코드(문제에 따라 선택)
      ...

      # 탐색할 범위의 재귀함수 동작
      dfs(...)
      dfs(...)
      dfs(...)

      # 이 부분까지 왔다면, 중간에 멈추지 않고 끝까지 탐색을 마친 경우이다.
      return True
  
  # 추가 탐색 가능 조건에 맞지 않을 때:
  return False

 

 - 그래프에서 재귀구조 (해밀턴 경로)

graph = [
 1: [2,3,4],
 2: [5],
 3: [5],
 4: [],
 5: [6,7],
 6: [],
 7: [3],
]

def recursive_dfs( v, discovered=[] ):
 discovered.append(v)
 for w in graph[v]:
   if not w in discovered:
     discovered = recursive_dfs(w,discovered)
   return discovered

 - 오일러경로