이건 재귀에 대한 공포증이나 어설프게 알고 있던 생퀴들을 위한 "재귀에 대한 해부학" 두번째 이야기야.


존나 재귀를 기계적으로 해부하고 틀을 만들어낸 거지. 사이언스의 영역이지. 하지만, 그냥 틀을 바로 이용할 수는 없고 주어진 문제에 맞게 커스텀 해야됨. 여기서 부터는 아트의 영역이 된다. 그래서 니가 재귀를 자유자재로 쓰려면 아트와 사이언스가 동시에 되야 됨


니가 상호참조를 이해하게 되면 트리나 그래프 관련 알고리듬은 걍 일단 돌아가게 만들 수 있다 (알고리듬 최적화와는 별개로)



* 상호참조 재귀


니네 족보를 보자. 니네의 후손의 미래는 니네가 모솔 탈출 전에는 확정이 안되니 조상만 보자. 니네 조부, 조모는 니네 아버지를 낳고, 니네 외조부, 외조모는 니네 어머니를 낳고 ... 너까지. 이걸 프로그램으로 표현하려면 Person 같은게 있어야 됨.


Person = [name, children], children = [] or [Person...]


1. Person을 보면 children에서 재귀가 일어난다. 이건 자기참조 재귀

2. 니가 children에 있는 개개의 Person을 처리하려 보면, 각각이 1로 재귀. 이건 상호참조 재귀


그림을 그려보면 알겠지만 트리구조가 됨. 이런 경우는 자기참조 및 상호참조가 있기 때문에 상호참조 재귀를 이용해야 된다.


define fn-for-thing (thing)

  ???thing-combine(thing,

                   fn-for-things (???things-from thing))


define fn-for-things(list-of-things)

  if (empty? list-of-things)

     ???result

  else

     ???things-combine(fn-for-thing(first(list-of-things)),

                       fn-for-things(rest(list-of-things)))


니들이 항상 주목해야 될게 단수형 thing과 복수형 things야. 그걸 보고 해당 함수에서 무엇을 인자로 받아서 무슨 일을 해야 하는지 지표로 삼아야지 안그러면 존나 헷갈리게 됨.


???가 붙은 부분은 무슨 작업을 하냐에 따라 니가 바꿔줘야 되는 부분이지. 어떤 경우에는 개념만 유지하고 코드구조는 약간 바꿔야 되기도 한다.


연습) 니네 족보를 표현하는 데이터 구조를 만들고, 위의 재귀를 이용해서 니네 조부모와 외조부모를 가르키는 톱 노드에서 너를 찾아내는 재귀함수를 만들어 봐라라