😃 안녕하세요. 휴먼스케이프 loowin입니다. 😃
오늘은 휴먼의 공통 교양책인 [코틀린으로 함수형 프로그래밍 시작하기]의 3장 재귀에 대해 알아보겠습니다.
https://blog.insightbook.co.kr/2019/12/12/%EC%BD%94%ED%8B%80%EB%A6%B0%EC%9C%BC%EB%A1%9C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%ED%95%A8%EC%88%98%ED%98%95-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%B0%8D/
재귀함수라니..!!
함수형 프로그래밍에서는 명령문을 반복할 때 루프 대신 재귀를 사용합니다.
함수형 프로그래밍의 특징 불변성(Immutable)의 장점을 살리기 위해서 재귀함수를 사용합니다.
함수형 프로그래밍에서 재귀
함수형프로그래밍에서는 어떻게(how) 값을 계산할 수 있을지 선언하는 대신 무엇(what)을 선언할지를 고민해야 합니다.
순수한 함수형 언어 하스켈은 반복 명령어를 아예 제공하지 않습니다. 하지만 코틀린은 멀티 패러다임 언어이기 때문에 반복 명령어를 지원합니다.
모든 반복문은 재귀로 구현할 수 있고, 모든 재귀도 반복문으로 구현할 수 있습니다. 재귀는 반복문에 비하여 복잡한 알고리즘을 간결하게 표현할 수 있지만,
다음과 같은 문제점을 가집니다.
동적 계획법 방식에 비해서 성능이 느립니다.
스택 오버플로 오류(stack overflow error)가 발생할 수 있습니다.
이 같은 문제점을 해결하는 방법에 대해 알아 보기 전에 재귀함수 예제들을 보며 재귀함수가 실행되는 과정을 살펴보겠습니다.
재귀를 설계하는 방법 재귀
“Hello”를 출력하는 프로그램을 재귀 함수로 작성해 보겠습니다.
Hello 재귀함수
“Hello”가 화면에 무한히 출력될 것입니다. 종료를 위한 조건이 없기 때문입니다.
종료 조건이 추가된 재귀함수
helloFunc 함수가 자기 자신을 다시 호출 할 때, 입력 매개변수로 받은 값 n을 감소 시켜주고 있습니다. 재귀를 반복하면 n이 1씩 감소되고, n이 0보다 작아지면 프로그램은 종료됩니다.
재귀함수 설계 방법
재귀가 무한루프에 빠지지 않으려면 재귀에서 빠져 나오는 종료조건(edge condition)이 적어도 한 개 이상 존재해야 하고 재귀를 반복할수록 종료조건으로 수렴해야 합니다.
종료조건(edge condition) 정의
함수의 입력을 분할하여 어떤 부분에서 재귀 호출을 할지 결정
함수의 입력값이 종료조건으로 수렴하도록 재귀 호출의 입력값을 결정
재귀가 수행되는 흐름 관찰해 보기
1부터 5까지를 더하는 프로그램을 구현해서 실행해 보겠습니다.
1부터 5까지 더하는 프로그램
내부적으로 재귀가 수행되는 흐름을 확인해 보겠습니다.
재귀 수행되는 흐름
종료조건을 만날 때까지 재귀 함수가 반복 호출된 후에 거꾸로 뒤에서부터 값이 더해집니다.
재귀 함수 설계 방법을 사용하여 코드를 구현하기
maximum은 순서가 있는 값들의 리스트를 받아서 가장 큰 값을 돌려주는 함수입니다. 이 함수를 재귀로 구현해 보겠습니다. 먼저 종료조건(edge condition)을 정의해야 합니다. 다음과 같이 각 리스트의 상태에 따른 maximum 함수의 결과를 생각해 보겠습니다.
입력 리스트가 비어 있을 경우, 최댓값을 구할 수 없기 때문에 오류가 발생한 후 종료될 것입니다.
입력 리스트에 구성요소가 한 개인 경우, 그 값이 최댓값이므로 종료될 것 입니다.
입력 리스트에 구성요소가 여러 개인 경우는 다음과 같습니다. 리스트의 첫 번째 값이 나머지 값들의 최댓값보다 크다면 첫 번째 값이 최댓값입니다. 나머지 값들의 최댓값이 첫번째 값보다 크다면 나머지 값들의 최댓값이 입력 리스트의 최댓값입니다.
이제 정리된 조건들을 고려해서 maximum 함수를 작성해보겠습니다.
maximum 함수
maximum 함수는 입력 리스트를 items으로 받아 리스트 내의 최댓값을 반환합니다. 앞에서 정리한 maximum 함수의 특징을 기반으로 종료조건을 정의하고, 그대로 구현하였습니다. 그리고 종료조건에 부합하지 않는 경우에는 리스트를 head와 tail로 나누고, head가 maximum(tail)보다 크면 head를 반환하고, 그렇지 않으면 maximum(tail)을 다시 호출하였습니다. 이런 일련의 호출 과정을 나열하면 아래와 같습니다.
재귀가 수행되는 흐름
호출과정을 머릿속으로 그려보는 연습을 통해 재귀를 통해서 최댓값 8이 반환되는 과정을 쉽게 이해할 수 있었습니다.
위의 2가지 예시들을 통하여 재귀함수가 실행되는 과정에 대해 이해해 보았습니다.
다음장에는 재귀함수의 성능을 개선하는 방법에 대해 알아보겠습니다.
이상! [코틀린으로 함수형 프로그래밍 시작하기]의 3장 재귀함수에 대한 요약이었습니다.
다음장 재귀 함수의 성능개선도 기해해주세요 😃
Get to know us better! Join our official channels below.
Telegram(EN) : t.me/Humanscape KakaoTalk(KR) : open.kakao.com/o/gqbUQEM Website : humanscape.io Medium : medium.com/humanscape-ico Facebook : www.facebook.com/humanscape Twitter : twitter.com/Humanscape_io Reddit : https://www.reddit.com/r/Humanscape_official Bitcointalk announcement : https://bit.ly/2rVsP4T Email : support@humanscape.io
가입하기
