어제 안드의노예가 재귀에 대한 지적 갈망을 표현해서 형이 관대하게 알려주기로 함. 잡설 피하고 바로 핵심으로 짬뿌하자.


* 자료구조가 자기참조나 상호참조로 인해 크기를 정할 수 없는 경우 재귀가 일어난다

(용어)

자기참조 - 지가 지 스스로를 가리키는 상태

상호참조 - 둘 이상이 엮이면서 서로 상대방을 가리키는, 마치 탁구시합하는 경우와 같은 상태


조팝들은 상호참조는 아직 어려우니까 일단 자기참조에 대해서 알아보자.



* 자기참조 (수학적 귀납법 같은 거임)

최소 한번은 자기참조가 안 일어나는 경우가 존재 (베이스 케이스라 부르자)

최소 한번은 자기참조가 일어나는 경우가 존재 (자기참조 케이스라 부르자)


이렇게 되면 재귀가 됨


익숙해지면 여기저기에 재귀를 적용할 수 있지만, 조팝 상태에선 어려우니 일단 데이터를 보고 자기참조가 일어나는지에 주목하자


* 데이터의 자기참조

프갤 닉들의 리스트 (스트링의 리스트)가 자기참조 구조의 데이터가 될 수 있다. 이런 경우 보통 니가 리스트 크기가 얼마가 될지 모르고 자유분방하게 늘거나 줄어들 수 있기 때문에 재귀로 생각하면 쉬움 (마치 집합 표현에서 조건 제시법 같은 거라 보면 됨)


- 아무 닉도 포함 안된 경우인 리스트 (베이스 케이스)

- 하나 이상의 닉이 포한 된 경우인 리스트 (자기참조 케이스)

이걸 list-of-nick 이라고 하면

- list-of-nick = ()

- list-of-nick = push("야이미친", list-of-nick)  // 요기서 자기 참조가 일어난다


* 자기참조가 일어날 때의 재귀 함수

먼저 데이터가 어떤 구성인지 확인해라. 입력 데이터가 자기참조를 가지고 있어야 됨. 이러면 어떤 문제냐에 상관없이 재귀를 사용할 수 있다.

문제가 주어지면 출력값에 주목해야 됨. 왜냐하면 문제가 바뀜에 따라 재귀함수에서 바뀌는 부분은 입력값은 동일한 구조지만 출력값이 모양이 바뀌거든


ex) 갤에서 쓰는 닉 = String, 그거의 리스트면 ListOfString (타입이나 클래스라고 생각하면 됨)


저런 데이터 구조인 경우 재귀함수는 항상 기계적으로 다음과 같은 구조가 됨

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

   if (empty?(list-of-things)) // 베이스 케이스

      ???some-result // 베이스 케이스 결과 값

   else ???combine-fn(first(list-of-things), // 베이스 케이스와 자기참조 케이스로 바꿔서 처리한후, 둘의 결과를 합침

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


???로 시작하는 부분이 뭘하냐에 따라 니가 채워야 되는 부분이야.

???some-result는 베이스 케이스에 대해 결과를 리턴하는 부분

???combine-fn은 보면 알겠지만, list-of-things에서 첫번째 꺼만 꺼내서 재귀가 안 일어나는 단순한 경우와 첫번째 부분을 제외해서 다시 재귀가 일어나게 하는 경우, 이렇게 두 경우를 합치는 거야. 첫번째 부분은 답을 내기가 쉬우니까 그걸 답을 바로 내고, 첫번째 부분을 제외한 거에 대해서는 다시 재귀를 돌려서 단순한 경우로 바꿔 풀게 하는 거지.


연습) 가끔 누가(관노 였든가) 갤에 월급루팡 리스트를 올린다. 재귀로 톱 월급루팡을 찾아내는 함수를 만들어 봐라. 입력으로는 각 닉에 대해 [닉,싼글 수] (NickCount 구조라고 생각해도 좋다), 리스트는 ListOfNickCounts - ["야이미친", 12], ["코세", 13], ...), 출력값은 NickCount - ["ㅇㅇ", 123]. 저 위에 있는 재귀함수 틀을 이용할 것. 저 위에 틀은 존재하지 않는 언어로 짠거니까 니가 익숙한 언어로 바꿔도 됨.


자기참조 세줄요약:

1. 입력이 되는 데이터와 출력이 되는 결과를 명확히 파악해라

2. 입력 데이터에서 베이스 케이스와 자기참조 케이스를 파악해라

3. 위 재귀함수 틀을 이용해서 베이스 케이스에서 출력값에 한걸음씩 다가가게 만들어라 



반응 시답지 않으면 이거로 바로 시리즈 종료 함 ㅎㅎ