재귀 생각법

2022-6-5 하스켈 학교 디스코드에 올렸던 내용을 정리해서 올립니다.

재귀 방식으로 생각하기 어려울 때를 위한 “생각법”을 고민해 봤습니다. 하나가 딱 딱 끝나고 다음으로 넘어가지 않는 재귀는 정말 생각을 귀찮게 하는 것 같습니다.

rec0 (x : y : z : []) = 1 + rec1 (y : z : [])
rec1 (y : z : []) = 1 + rec2 (z : [])   
rec2 (z : []) = 1 + rec3 []    
rec3 [] = 0    

이렇게 먼저 생각 후 rec(n)들의 공통된 동작을 본다면 아래로 생각이 연결됩니다.

rec (x : xs) = 1 + rec xs
rec [] = 0

어떤가요? 도움이 되시나요?
당연히 익숙한 분들을 위한 게 아니라, 재귀가 익숙하지 않은 분들을 위한 내용입니다.

함수형은 경우의 수 중에 한가지만 있다고 생각하는 게 아니라 모든 경우의 수(상황)가 이미 다 있고, 그 중에 하나를 고른다(매핑한다)는 생각법이 도움이 될 때가 많은 것 같습니다. 여기서 아이디어를 얻어, 실제 재귀 함수가 100번을 돈다면 100개의 함수가 따로 있다고 생각하고, 공통 동작을 나중에 하나의 함수로 추상화한다는 “의식의 흐름”입니다. 유한한 메모리는 컴퓨터가 가지고 있을 뿐, 우리 생각 자체를 유한하게 할 필요는 없습니다. 모든 경우의 수는 이미 존재하고, 그 중에 하나를 고를 뿐입니다.

추가
- 재원님께서 비슷한 아이디어로 Y Combinator를 설명한 글을 알려주셨습니다. - The Y Combinator - 실제로 텍스트로 본 적은 없는데요, 엘룬님의 조언에 따르면, 위 방식이 이론적으로 재귀를 설명하는 방식이라 합니다.

2024-1-7 추가 - 무한 재귀
선언형 프로그래밍처럼, 생각을 선언과 정의로 분리하는 방법입니다.

• infiniteList는 무한히 재귀 도는 것이라 선언한다.
  이 단계에서 정의는 모릅니다. 그저 무한히 재귀 돌거라고 선언만 했습니다.

• 이제 infiniteList를 정의한다.
  앞에 선언했던, “선언”은 “언젠가 정의 되겠지”하고 무책임하게 넘어 갑니다.
  (:) 1함수에 무한 리스트를 마치 평범한 값이나 함수 처럼 넣어주면 됩니다.
  1 : infiniteList

• 이제 앞에 선언과 정의를 붙이면 됩니다. 선언은 필요할 때 정의를 가져오면 됩니다.
  infiniteList_정의 = 1 : infiniteList_선언

• 필요한 때는 infiniteList가 정하는 게 아니라, 누군가, take같은 파트너가 알려 줄 겁니다.

선언해서 먼저 써먹고, 나중에 정의로 바꾸면 됩니다. 선언을 정의로 바꾸는 건 내가 할 일이 아니라, 컴퓨터가 할 일입니다. 너무 책임감을 가지고, 미리 걱정하지 않는 게 좋습니다.

저는 재귀를 계속 보다 보니, 지금은 위와 같은 방식으로 생각하게 되어, 처음보다는 더 빨리 재귀를 떠올리고 있습니다. 하지만, 이 것만이 가장 효율적인 생각 방식이라고 보지 않습니다. 또, 생각이 발전하면 또 남겨두도록 하겠습니다.