8. 재귀(recursion)

• '평범한 한글'은 함수형 언어이다.

• 명령형 언어가 아니기 때문에 문제를 해결할 때 함수형 언어의 기법을 먼저 고려해야 한다.

• 명령형 언어에서 문제를 풀 때 가장 많이 사용하는 것이 '반복'이다.
• 상태 변수를 하나 이상 설정하고 이 변수의 조건에 따라 반복 여부를 결정한다.
• for 루프의 인덱스 변수나 while 문의 조건 변수는 다 이 범주에 속한다.
• 뎡령형 언어의 '반복'은 부작용을 동반한다. ⇒ 순함수가 아니다!

• '평범한 한글'에서는 이러한 명령형 언어의 처리 방식을 지원하지 않는다. (그리고 앞으로도 이러한 기능이 추가될 계획도 없으리라 본다.)
• 함수형 언어의 해결 방법이라면 순함수를 쓰는 것이 원칙이다. 언젠가 '평범한 한글'이
  
  Haskell 의 모나드를 가져와서 상태 변화를 다룰 수 있을 지도 모르지만 그것 역시 함수형 언어의 방식이지 명령형 언어의 방식은 아니다.

• 순함수를 사용해서 반복적인 문제를 풀려면 '재귀'와 '중첩 함수'를 써야 한다.

• 이런 방법은 상태 변화를 동반하지 않는다. ⇒ 부작용이 없다.

재귀가 무엇일까?

• 재귀: 자신을 정의할 때 자신을 이용하는 것.
• GNU is Not Unix
• 이것이 재귀이다. ← 왼쪽 링크를 누르면 아무 변화가 없어보이지만, 사실은 지금 이 페이지에 링크를 건 것이다.

• 실생활에서의 재귀
• 마트료시카: 러시아의 전통 인형. 큰 인형 안에 작은 인형이 있고, 그 안에 다시 작은 인형이 있고....
• 프랙탈: 큰 모양 속에 똑같은 형태의 작은 모양이 들어 있고, 그 모양 속에 다시 작은 모양이.....
• 두 개의 거울로 나를 비추어 보면, 거울 속의 나, 그 속의 나, 그 거울 속의 나......

• 재귀 함수: 함수를 정의할 때 자기 자신을 포함하는 함수.

• 대표적인 재귀 함수의 예
• 계승(factorial)
• 좌변에서 을 정의하기 위해 우변에서 다시 을 사용.


Python



Haskell 코드

def factorial(n):
	if n == 0: return 1
	else: return factorial(n - 1)

factorial 0 = 1
factorial n = n * factorial (n - 1)

• 피보나치 수(fibonacci number)
• 좌변에서 을 정의하기 위해 우변에서 다시 를 사용


Python ,



Haskell 코드

def fib(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fib(n-1) + fib(n-2)

fib 0 = 0
fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

자기 자신 = ㄱ ㅇ

• 다은 언어들은 함수를 정의할 때 이름을 붙인다.
• 함수 정의를 시작할 때 썼던 이름을 함수 몽톰에서도 쓸 수 있다.

• '평범한 한글'은 함수를 정의할 때 이름을 붙이지 않는다.
• 함수 몸통에서 무슨 수로 자기 자신을 나타낼 수 있을까?

• 함수의 구조
• [함수 몸통] ㅎ

• 가장 간단한 함수. 숫자 3을 내놓는 함수부터 만들어 보자.

ㄹ ㅎ

• ㄹ은 함수 몸통이고 ㅎ 은 함수를 정의하는 단어이다.

• 위의 코드를 실행하면 함수 객체를 내놓는다. 평범한 한글은 함수 객체를 "최상위 깊이에서 만든 함수"처럼 표시한다.

ㄹ ㅎ ㅎㄱ

• ㄹ ㅎ 함수를 인자 없이 호출하려면 ㅎㄱ 처럼 쓴다. 숫자 객체 3을 내놓는다.

• '평범한 한글'의 함수 몸통에서 자기 자신을 나타내려면 ㄱ ㅇ 을 사용한다.

ㄱ ㅇ ㅎ ㅎㄱ 

• ㄱ ㅇ ㅎ은 자기 자신을 내놓는 함수이다.

• 이 함수를 ㅎㄱ으로 인자 없이 호출했더니 자기 자신을 내놓았다. ㄹ 자리에 ㄱ ㅇ이 왔다고 생각하면 쉽다.

• 함수 객체는 ㅎㄱ 처럼 호출할 수 있다.

ㄱ ㅇ ㅎㄱ  ㅎ ㅎㄱ

• ㄱ ㅇ ㅎㄱ ㅎ 은 자기 자신을 호출하는 함수이다.

• 이 함수를 ㅎㄱ 으로 호출하면 자기 자신을 호출하고, 그러면 다시 자기 자신을 호출하고, 그러면 또 자기 자신을 호출하고.... 이 행동을 반복한다. 그러다가 호출 스택이 가득 차면...

• "문제가 생겼습니다. RangeError: Maximum call stack size exceeded."라고 오류 메시지와 함께 프로그램이 비정상적으로 끝난다.

• 위의 메시지는 "호출 스택의 최댓값을 초과하였습니다"라는 뜻이다.

종료 조건 구현

• 재귀 함수가 자신을 계속 부르기만 한다면 결국 오류에 빠진다.

• 쓸모 있는 재귀 함수는 "종료 조건"(edge condition)을 갖고 있어야 한다
• factorial 함수의 종료 조건은 factorial(0) = 1
• fib() 함수의 종료 조건은 fib(0)= 1

조건에 따라 다른 값 내놓기

• '평범한 한글'에서 조건에 따라 다른 값을 내놓으려면 False 나 True, 즉 논리값을 함수로 호출한다.
• True: 두 개의 인수 중 첫 번째 인수를 내놓는다.
• False: 두 개의 인수 중 두 번째 인수를 내놓는다.

ㄱㅇㄱ ㅈㅁㅈㄴㄱ (ㄱㅇㄱ ㄷㄴㄱ ㅈㅎㄷ) ㅎㄷ ㅎ

• 인수를 받아서 10보다 작으면 인수를 그대로 내놓고, 10보다 크거나 같으면 999를 내놓는 함수다. ㅈㅁㅈㄴㄱ 는 999, ㄷㄴㄱ 는 10.

• ㄱㅇㄱ ㄷㄴㄱ ㅈㅎㄷ 는 함수가 받은 인수와 10이 작은지 비교해서 논리값을 만든다.

• 이 논리값을 호출(ㅎㄷ)하면, 참인 경우 인수(ㄱㅇㄱ)를 내놓고 거짓인 경우 999(ㅈㅁㅈㄴㄱ)를 내놓는다.

ㄱㄴㄱ 
ㄱㅇㄱ ㅈㅁㅈㄴㄱ (ㄱㅇㄱ ㄷㄴㄱ ㅈㅎㄷ) ㅎㄷ ㅎ ㅎㄴ 

ㄷㄴㄱ 
ㄱㅇㄱ ㅈㅁㅈㄴㄱ (ㄱㅇㄱ ㄷㄴㄱ ㅈㅎㄷ) ㅎㄷ ㅎ ㅎㄴ

• 위의 함수에 8을 넘기면 넘겨 받은 그대로 8을 내놓는다.

• 10을 넘기면 999를 내놓는다.

종료 조건 구현하기

• factorial 과 fib 함수의 종료 조건을 구현해보자.

ㄴ ㅈㅁㅈㄴㄱ (ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ

• 받은 인수가 0이면 1을 내놓고, 그 외에는 999를 내놓는다.

ㄱ 
ㄴ ㅈㅁㅈㄴㄱ (ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ ㅎㄴ 

ㅁ
ㄴ ㅈㅁㅈㄴㄱ (ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ ㅎㄴ

• 실제로 0과 4를 넣고 호출하면 제대로 결과를 내놓는 것을 확인할 수 있다.

계승 구현

• 계승(factorial)은 종료 조건이 아닐 때 n * factorial(n-1) 의 꼴을 가진다. 이 부분만 따로 때어 '평범한 한글'로 나타내보자.

(ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 

• 안쪽 괄호는 받은 인수(ㄱㅇㄱ)에 -1을 더하는(ㄴㄱ ㄷㅎㄷ) 코드다. 평범한 한글에는 뺄샘 연산자가 없기 때문에 -1을 더해주었다.

• 방금 구한 (n-1) 에 해당하는 (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) 를 인수로 넘겨서 자기 자신(ㄱ ㅇ)을 호출(ㅎㄴ) 한다.

• 받은 인수(ㄱㅇㄱ)와 방금 호출한 결과를 곱한다(ㄱㅎㄷ)

• 이제 위에서 작성한 부분을 종료 조건에서 구현한 999(ㅈㅁㅈㄴㄱ) 부분에 넣어보면 이렇다.

ㄴ  (ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 
(ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ

• 첫 번째 줄의 ㄴ은 종료 조건이 참일 때 실행된다.

• 첫 번째 줄의 (ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 는 인수 * 자기자신(인수-1) 이다.

• 두 번째 줄은 if (인수 == 0) 과 같은 부분이다.

• 이제 잘 동작하는지 인수를 넣어서 호출해보자.

ㄱ 
ㄴ  (ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 
(ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ ㅎㄴ 

ㅁ 
ㄴ  (ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 
(ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ ㅎㄴ 

ㅂ 
ㄴ  (ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 
(ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ ㅎㄴ 


ㄷㄴㄱ 
ㄴ  (ㄱㅇㄱ (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄱㅎㄷ) 
(ㄱㅇㄱ ㄱ ㄴㅎㄷ) ㅎㄷ ㅎ ㅎㄴ

• 재귀 함수를 시험할 때는 반드시 종료 조건이 제대로 잘 동작하는지 검사해야 한다.

• 제법 큰 값인 factorial(10) 도 잘 계산 해낸다.

피보나치 수 구현

여러 개의 조건 구현하기

• 피보나치 수의 종료 조건은 엄밀히 말하면 세 개이다. fib(0), fib(1), fib(2)

• 우선 두 개의 조건을 '평범한 한글'로 판별해보자. 인수로 0을 전달하면 1을, 1을 전달하면 3 을, 그 이외에는 5를 넘기는 함수를 만들어 보자.

ㄴ (ㄹ ㅂ (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ

• 먼저 ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ 는 인수가 1과 같은지 비교하고, 참이면 3을, 거짓으면 5를 내놓는다.

• 다음으로 ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ는 인수가 0과 같은지 비교하고, 참이면 0을, 거짓이면 앞에서 계산한 결과(1과 같으면 3, 아니면 5)를 내놓는다.

ㄱ 
ㄴ (ㄹ ㅂ (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄴ 
ㄴ (ㄹ ㅂ (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄷ 
ㄴ (ㄹ ㅂ (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄹ 
ㄴ (ㄹ ㅂ (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄱㄴㄱ
ㄴ (ㄹ ㅂ (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

• 위의 함수에 차례로, 0, 1, 2, 3, 10을 넣어서 호출해 보면, 0과 1일 때는 각각 1과 3을 내놓고, 그 외에는 5를 내놓음을 확인할 수 있다.

• 세 개의 조건도 다르지 않다. 인수로 0, 1, 2를 넘기면 각각 1, 3, 5를 내놓고, 그 이외에는 7 을 내놓는 함수이다.

ㄴ (ㄹ (ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ)) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ

• 위의 코드에서 좀 더 알아보기 쉽게 괄호를 고쳐 쓰면 이렇게 표현할 수 있다.

ㄴ ㄹ ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ

• 실제로 인수를 전달해서 실행해보자.

ㄱ
ㄴ ㄹ ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄴ
ㄴ ㄹ ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄷ
ㄴ ㄹ ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄹ 
ㄴ ㄹ ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

ㄱㄴㄱ
ㄴ ㄹ ㅂ ㅈ (ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ ㅎㄴ

• '평범한 한글'의 함수 호출 방법 때문에 굉장히 독특한 형태로 코드가 만들어진다.

if 조건 1:
	return A
elif 조건 2:
	return B
elif 조건 3:
	return C
elif 조건 4:
	return D
....
else
	return Z

• 위의 코드는 '평범한 한글'로 다음과 같이 쓸 수 있다.

A B C D .... Z .... (조건 4) (조건 3) (조건 2) (조건 1)

• Z 값은 모든 조건이 맞지 않을 때, 즉 가장 아래쪽 else 일 때 내놓을 값이다. 각 조건에 해당하는 값과 조건이 Z 값을 중심으로 좌우 대칭으로 짝을 이룬다고 생각하면 기억하기 편리하다.

피보나치 수 구현하기

• 함수의 종료 조건이 세 개이고, 한 개의 함수 몸통을 갖는 fib 함수는 다음처럼 구현할 수 있다.

ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ 

• 여러 조건을 연결하는 패턴을 참고하면 위의 코드를 이해하기가 훨씬 쉽다.

• 종료 조건을 준비하기 위해 각각 0, 1, 1을 쓰고 있다.

• (ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱ ㅇ ㅎㄴ 는 자기자신(인수 - 1) 과 같다. 마찬가지로 (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱ ㄴ ㅎㄴ 는 자기자신(인수 - 2)이고, 이 둘은 ㄷㅎㄷ로 더해진다.

• 아래에 있는 세 개의 괄호는 종료 조건을 의미한다. 각각 인수 == 2, 인수 == 1, 인수 == 0 과 같은 의미이다.

• '평범한 한글'에서 ㅇ과 ㅎ은 그 앞에 공백이 있는 것과 없는 것을 똑같이 취급하기 때문에 ㄱ ㅇ ㅎㄴ는 ㄱㅇㅎㄴ로 줄여 쓸 수 있다.

ㄱ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 

ㄴ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 

ㄷ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 

ㄹ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 

ㅁ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 

ㅂ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 

ㅅ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ 


ㅈ
ㄱ ㄴ ㄴ ((ㄱㅇㄱ ㄴㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ (ㄱㅇㄱ ㄷㄱ ㄷㅎㄷ) ㄱㅇㅎㄴ ㄷㅎㄷ)
(ㄱㅇㄱ ㄷ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄴ ㄴㅎㄷ ㅎㄷ) (ㄱㅇㄱ ㄱ ㄴㅎㄷ ㅎㄷ) ㅎ  ㅎㄴ

재귀 함수 패턴

• '평범한 한글'에서 재귀 함수를 작성할 때 다음과 같은 패턴을 쓸 수 있다.

종료조건1_값 종료조건2_값...
함수 몸통
...종료조건_2 종료조건_1

• 마지막으로....

부작용이 없는 모든 반복문은 재귀 함수로 작성할 수 있다!

⚠️

재귀의 낯설음 프로그래밍을 공부할 때 '명령형 언어'로 시작한 대부분의 사람들은 반복해서 문제를 풀 때 재귀 보다 루프를 훨씬 편하게 생각한다. '명령형 언어'는 절차를 중시하게 때문에 "문제를 어떻게 풀까"를 고민해야 하고 뼛속까지 절차적인 사고가 베어 있으면 그만큼 재귀를 이해하기 어려울 수밖에 없다. 물론 나도 그랬다. 함수형 언어는 "무엇이 문제인가"를 고민한다. 다른 말로 하면 "어떻게 문제를 설명할까"에 초점을 맞춘다. 프로그램의 흐름 보다는 문제 자체를 어떻게 정의하는지를 중요하게 생각하기 때문에 처음에는 굉장히 낯설 지도 모른다. 하지만 문제를 정의하는 방법에 익숙해진다면 굉장히 깔끔하고 읽기 쉬운 코드가 나온다. ('평범한 한글'은 난해한 언어이니까 읽기 어렵겠지만

Haskell 이라면 충분히 읽기 좋은 코드를 만들 수 있다.) 절차적 생각에 익숙한 사람들은 재귀가 가진 문제점을 지적한다. 1) 프로그램의 흐름을 이해하기 어렵다. 2) 폰 노이만 기계의 특성 상 재귀가 루프보다 느리다. 3) 호출 스택에 계속 정보를 쌓아야 하기 때문에 메모리를 많이 소비한다. 4) 호출 스택이 깊지 않다면 재귀 함수를 실행하다가 스택이 넘칠 수 있다. 이 문제들은 사실이지만 그렇기 때문에 재귀를 꺼려할 필요는 없다. 오히려 적극적으로 재귀를 사용해서 문제를 풀어보는 습관이 중요하다. 1)은 아직 함수형 언어로 문제를 푸는 방법에 덜 익숙해서 생기는 문제이고, 2)와 3)은 일반적인 경우에는 치명적인 문제를 일으키지 않는다. 여러분이 쓰는 컴퓨터는 어마어마한 능력과 자원을 가지고 있다. 4) 역시 호출 스택이 우리가 생각하는 것보다는 훨씬 깊으며, 언어의 실행 환경에서 호출 스택의 깊이를 조절하는 기능을 제공하기도 한다. 낯설음은 사람을 불편하고 두렵게 만든다. 어쩌면 '편함은 불편함에 익숙해지는 것'인지도 모르겠다.