재귀
귀납(Induc) 개념에서 비롯한 프로그래밍에서의 재귀(recusion)
우물 안 개구리는 바다를 이야기할 수 없다. 메뚜기에게는 얼음을 이야기할 수 없다. - 장자
중학교 때였던가, 고등학교 때였던가 가물가물하지만, 과학 과목들(물리, 화학, 생물, 지구과학) 중 한 담당 과목 선생님이 '연역과 귀납의 차이'를 쉽게 암기하는 방법을 알려줬다. 일반적 ☞ 구체적 순서이면 앞글자 'ㅇ'을 연상해서 연역법, 구체적 ☞ 일반적 순서이면 앞글자 'ㄱ'을 연상해서 귀납으로 생각하면 된다는(!).
그때 이후로 연역과 귀납에 대해서 별 고민 없이 뭐가 뭔지 쉽게 분간할 수 있었다. 말인즉슨 구체적인 사례를 통해 일반적인 명제를 이끌어내면 귀납이라고 쉽게 갈피를 잡을 수 있었던 바야흐로 나이 서른여덟 먹고 다시 '프로그래밍'을 혼자 독학하면서 귀납(induction)의 개념을 들추고 심지어, '러시아 농부의 곱셈 계산 알고리즘'까지 실습하고 있다.
컴퓨터에서의 귀납(induction, 인덕)도 학창 시절에 배웠던 과학적인 사고로 증명을 하는 방법론 중인 하나인 귀납과 같이 수많은 사례를 통해 하나의 식으로 자연수의 범위를 구체적으로 입증한다. 코딩할 때 이 귀납(induction)이라는 개념을 빌려와서 재귀적인(recursive) 구조인 *재귀 함수까지 만든다.
귀납 정의는 아래와 같다.
0. 문제 제기 : 0부터 n까지의 수가 자연수인지 아닌지를 어떻게 증명할까?
1. 귀납 정의
0) 기초(base) : 0은 자연수이다.
1) 귀납(induction) : 0이 자연수이면 0 + 1도 자연수이다.
1 이 자연수이면 1 + 1 도 자연수이다.
2 가 자연수이면, 2 + 1 도 자연수이다.
....
즉, n이 자연수이면 n + 1도 자연수이다.
2) 이 외에 다른 자연수는 없다.
일단 수의 범위를 자연수로 한정해서 내리는 자연수의 귀납 과정을 활용하여 아래와 같이 자연수 n까지의 누적 합을 계산하는 재귀 함수(recursive funciton) 도 만들 수 있다.
0. 문제 제기 : 0부터 n까지의 자연수의 합을 어떻게 구할까?
1. 귀납 과정을 활용한 재귀 함수
0) 0은 자연수이므로 n = 0 은 증명할 것도 없이 자연수이다. [Base]
1) 만약 n이 0보다 크면( n > 0 ), 위의 귀납의 정의에 따라 n + 1도 자연수이다. [Induction]
2) 위의 0), 1) 과정에서 나온 자연수 이외에 자연수는 없다.
위의 1)에서 n > 0 보다 크면이라는 제어 조건은 n의 값이 1씩 감소하면서 계속 반복하므로(자신을 다시 참조하게 되므로) 반복 조건이라고 한다. 그리고 1)의 n = 0 조건은 n이 0보다 작은 값은 없으므로(계산을 끝나게 하므로) 종료 조건이라고 한다.
귀납의 정의를 sigma(n)의 식으로 표현하면 아래와 같다.
0 (n = 0, 종료 조건)......... 귀납 정의의 1)
sigma(n+1) = sigma(n) + n+1 (n > 0, 반복 조건)......... 귀납 정의의 2)
1부터 n까지의 합을 수학 용어로 시그마(sigma, ∑)로 칭하고, sigma(n)으로 표현한다. 그리 sigma(n+1)은 위의 식과 같이 n까지의 합을 이미 구한 sigma(n)과 n+1(마지막수)을 더하면 된다. 이미 구했다는 표현에서 알 수 있듯이, 좌변의 sigma가 우변에 다시 사용되어서(재사용, rewriting) 이러한 구조의 식을 '재귀식(recusive expression)'이라고 하고, 이 재귀식은 자신을 참조하므로 '재귀 함수'라고 한다..
필자가 이 재귀의 개념을 환기시키는 마당에 스스로 긁적여서 개념을 정리해봤는데, 아마도 누군가 읽고 단번에 이해하신다면 필자도 제대로 이해했다고 볼 수 있겠지만, 대부분의 필자의 글이 이해하기 어렵다고 들은 바가 있어 필자 역시 미숙한 이해 상태에서 개념 환기를 했다는 것을 반증했으리라. 사물로 치면 아래 그림의 앵무조개나 프랙탈 구조와 같다.
앵무조개의 계속 크기가 감소(피보나치수열)하며 반복되는 나선형의 모양은 재귀 구조다. 
고사리 같은 양치식물에서 볼 수 있는 자기 닮음 패턴, 프랙탈 차원의 이론까지 끄집어내는 패턴의 과학 [1]: 패턴의 자기 닮음꼴과 프랙털 차원 – 과학의 지평 사이트(하단 참하지만 교과서 같이 정석의 느낌이 물씬 나는 참조 서적은 저자 도경구 교수가 한양대 에리카에서 수년간 쌓은 강의 노하우가 그대로 느껴진다. 이 책의 뒤표지의 추천글을 올리신 분들의 이름 중 컴퓨터 서적을 많이 봐왔었다면 어디서 봤을법한 이름도 있고 그의 말 한마디로 인해 책의 내공이 느껴질 만도 하다. '컴퓨터 세계가 여는 세상'을 지은 이광근 교수(한국인 중 아마도 드물게 미국의 벨연구소-전화기를 최초로 발명한 벨의 그 벨 연구소-에서 연구한 이력이 있다)의 추천 어록이었기 때문이다.
필자는 한양대 에리카 캠퍼스 근처에 발디뎌본 적도 없는 가방끈이 짧은 사람이다. 하지만 책의 저자의 유튜브 직강으로 또 한 번 개념 환기가 가능하고, 실습 문제 또한 재밌다. 필자가 즐겨했었던 '블랙잭' 게임이 프로젝트 마지막 과제로 기다리고 있다. 이번 4장을 기본으로 9장까지 계속 재귀의 개념은 등장한다. 일전에 파이썬을 통한 알고리즘 개념을 공부하면서 한 번 스탠퍼드대 강의에서 소개한 영상을 통해 대강 보고 지나쳤는데, 프로그래밍에서 메모리 공간을 낭비하지 않기 위해 필수적으로 알아둬야 하는 기본 코딩 지식이라는 것을 알았다.
즉, 재귀 개념을 앎으로써 얻는 부가적인 지식은 다음과 같다.
1. 메모리 관리 능력(*폴리글랏 프로그래밍)
: C/C++과 같은 언 매니지드 언어가 어려운 이유 중 하나가 메모리 관리(공간 절약)이다. 프로그래머가 메모리를 효율적으로 다루고 관리하는 능력이 얼마나 중요한지는 개발자에서 리딩 개발자로 넘어가는데 필수적이다. 비록 재귀 함수가 파이썬에서 많이 사용하는 while루프나 if 제어구조보다 재귀 함수의 공간 효율성이 떨어지긴 해도 대부분의 다른 언어는 재귀 호출 횟수에 제한이 없을 뿐만 아니라, 재귀 호출의 실행 성능도 루프 구조에 못지않게 좋다(도경구, 2021). 계산 대상이 되는 데이터의 구조(→자료구조)에 따라 재귀 함수로 코딩하면 훨씬 더 프로그램이 간결하면서 명료해지는 경우도 많기 대문에 반드시 익혀 두어야 한다고 한다.
2. 디버깅을 하는 능력
: "개발의 반이 디버깅이다"라는 말이 있는데, 디버깅은 개발과 보안(테스팅)에서 빠질 수 없는 능력이다. 저자는 매번 다루는 프로그램에서 '함수 호출의 실행 추적'을 통하여 손 코딩으로 디버깅(트래킹)을 할 수 있는 기회를 준다.
3. 재귀 함수 구조와 반복 구조의 성능 차이를 통해 계산비용 분석 능력
: 귀납 구조를 바탕으로 하향식(Top-down) 사고하여 재귀 함수를 구현하는 방법과 꼬리 재귀 함수를 통해 상향식(Bottom-up) 사고로 구현한 방법의 계산비용의 차이(공간의 효율)를 알려준다. 이 이전에 재귀 함수의 규칙적인 구조 변환을 통하여 재귀 함수의 구조가 상향식으로 사고하여 작성한 반복 구조(while-loop)와 사실 동일하다는 것도 알 수 있다. 이후 여러 알고리즘을 구현하는데 필요한 나눠 풀기 기법을 적용하여 프로그램의 실행 성능(시간의 효율)을 향상하는 방법도 알 수 있다.
*재귀 함수 : 함수의 몸체에서 함수 자신을 호출하는 것을 '재귀 호출(recursive call)'이라고 하고, 재귀 함수는 재귀 호출을 통해서 동일한 작업을 반복함.
참조
1) 도경구 (2021). 제어 구조의 설계 원리를 중심으로 배우는 프로그래밍의 정석 파이썬.
2) 패턴의 과학 [1]: 패턴의 자기 닮음꼴과 프랙털 차원 – 과학의 지평 (kias.re.kr)
