erlang : 재귀

대부분의 함수형 언어가 그렇듯, 얼랭도 for / while문을 제공하지 않는다. 이런 반복이 필요할 때, 재귀를 이용해서 하는 것이 필요하다. 

재귀 함수를 짤 때 팁

• 기본적인 조건일 때 어떤 행동을 해야하는지를 먼저 설정한다. 
• 종료 조건을 설정한다.
• 이후 기본적인 조건에 다음 재귀를 넣어준다. 

 

길이

들어온 리스트의 모든 길이를 구하는 함수를 구현해보자. 

len([]) -> 0
len(_) -> 1

기본 조건과 종료 조건을 확인하면 다음과 같다. 

len([]) -> 0;
len([_|T]) -> 1 + len(T).

여기에 추가적으로 재귀를 표현만 해주면 손쉽게 구현할 수 있다.

 

꼬리재귀

fac(N) when N == 0 -> 1;
fac(N) when N > 0 -> fac(N-1) * N.

재귀가 길어지게 될 경우, 수백만 개의 숫자를 메모리에 보관하거나 해야한다. 예를 들어 위와 같은 함수가 있다면 fac(10)을 구하기 위해서는 fac(9)의 값을 구해와서 10을 곱해야한다. fac(9)를 구해와서 10을 곱하기 위해서 10을 기억해두어야 한다. 그리고 fac(9)는 또 fac(8)이 필요하며 9를 기억해두어야 한다. 이처럼 어떤 식의 평가가 완료된 후 그 값을 곱해야하는 형태의 재귀는 메모리에 모든 값을 저장해야한다.

이럴 때는 꼬리 재귀를 이용해서 해결할 수 있다. 꼬리재귀는 위의 선형 프로세스(요소가 있는만큼 증가)를 반복 프로세스(실제로 커지지 않음)로 변환하는 방법이다. 방법은 간단하다. 값을 함수 단위에서 기억하지 않도록 필요한 연산을 해서 다음 함수로 넘겨주면 된다. 

tail_fac(N) -> tail_fac(N,1).

tail_fac(0,Acc) -> Acc;
tail_fac(N,Acc) when N > 0 -> tail_fac(N-1, N*Acc).

tail_fac(10,1)을 하게 되면, tail_fac(9, 10)을 구하면 된다. tail_fac(9,10)은 이 지점으로 돌아와서 어떤 값을 구할 필요가 전혀 없다. 따라서 그것을 기억하지 않고 바로 다음으로 넘어가는 형태로 구현된다. 이처럼 꼬리 재귀를 이용하면 한번의 식을 평가하는데 기억해두어야 하는 값이 2개 뿐이기 때문에 메모리를 아끼면서 넘어갈 수 있다.

tail_len(L) -> tail_len(L,0).

tail_len([], Acc) -> Acc;
tail_len([_|T], Acc) -> tail_len(T, Acc+1).

길이를 구하는 식은 꼬리재귀를 이용하면 다음과 같이 구현할 수 있다. 

 

 

재귀 추가 작업

Term을 N번만큼 반복하는 함수

duplicate(0, _) -> [];
duplicate(N, Term) -> [Term | duplicate(N-1, Term)].

위를 반복하려면 duplicate(N-1, Term)의 값을 불러와서 나중에 연산해야한다. 따라서 비효율적이다.

tail_duplicate(N, Term) -> tail_duplicate(N,Term,[]).

tail_duplicate(0, _, List) -> List;
tail_duplicate(N, Term, List) -> tail_duplicate(N-1, Term, [Term|List]).

위로 작업할 경우, 현재 있는 값만으로 충분히 연산할 수 있다. 따라서 돌아올 위치를 기억하지 않아도 되고, 다음 함수로 반복하는 형태로 실행된다. 

Term을 뒤집는 함수

reverse([]) -> [];
reverse([H|T]) -> reverse(T) ++ [H].

위 함수를 이용할 경우 reverse(T)의 모든 결과를 알아야 [H]를 더하는 연산이 가능할 수 있다. 따라서 모든 결과를 기록해두는 형태가 된다. 

tail_reverse(Term) -> tail_reverse(Term, []).

tail_reverse([], List) -> List;
tail_reverse([H|T], List) -> tail_reverse(T, [H|List]).

위 함수를 이용하게 되면 tail_reverse의 다음 결과를 몰라도 된다. 따라서 이 함수는 돌아올 위치를 기억하지 않고 재귀를 한다.

리스트에서 숫자만큼 서브 리스트 만들기

sublist([], _) -> [];
sublist([_|_], 0) -> [];
sublist([H|T], N) -> [H | sublist(T,N-1)].

리스트와 N을 주면, 리스트에서 N개만큼 순차적으로 값을 뽑아서 리스트를 만든다. 기본적으로 위와 같이 구현할 수 있다. 그렇지만 꼬리재귀가 되지 않아 문제가 발생한다. 

tail_sublist(L, N) ->
  tail_reverse(tail_sublist(L, N, [])).

tail_sublist(_, 0, List) -> List;
tail_sublist([], _, List) -> List;
tail_sublist([H|T], N, List) when N > 0  -> tail_sublist(T, N,  [H|List]).

이 경우 다음과 같이 구현하면 된다. 문제는 값이 전부 뒤집어져서 나오기 때문에 마지막에 tail_reverse()를 추가해서 다시 한번 뒤집어 주는 것이 중요하다.

 

파이썬 zip 함수 구현하기 

zip([],[]) -> [];
zip([H1|T1], [H2|T2]) -> [{H1, H2}|zip(T1,T2)].

zip 함수는 [1,2,3], [a,b,c]를 인자로 전달해주면 [{1,a}, {2,b}, {3,c}]의 아웃풋이 나온다. 위의 경우 zip(T1,T2)의 결과를 확인하기 전까지는 값이 마무리 되지 않는다. 따라서 스택에 값이 쌓인다

tail_zip(L1, L2) ->
  tail_reverse(tail_zip(L1,L2, [])).

tail_zip([], _, List) -> List;
tail_zip(_, [], List) -> List;
tail_zip([H1|T1], [H2|T2], List) -> tail_zip(T1, T2, [{H1, H2} | List]).

따라서 다음과 같이 accumulator를 만들어서 등록해주면 된다.  그런데 이 때, 기본적으로 사용하게 되면 값이 반대로 나오게 된다. 따라서 reverse() 함수를 이용해서 결과값을 한번 뒤집어 줘야 한다.

 

꼬리재귀의 TCO / LCO

TCO(Tail-Call optimisation)은 LCO에 포함되는데, LCO에서 좀 더 특별한 케이스를 의미한다. 함수의 마지막 부분(Tail)의 위치에서 자신을 호출하는 함수를 볼 때, 현재의 스텍 프레임을 제거하는 형태로 동작한다. 따라서 무한 반복하는 재귀는 메모리를 증가시키지 않는다.

LCO(Last Call Optimisation)는 함수의 마지막 식에서 다른 함수를 호출할 때 마다 발생한다. 함수의 마지막 식에서 다른 함수를 호출하게 되면, 얼랭 가상머신은 스택 프레임을 저장하지 않는다. 이런 이유 때문에 꼬리 재귀는 여러 함수들 사이에서도 가능하다. 예를 들어 a() ->  b(). b() -> c(). c() -> a().는 LCO가 Stack Overflow를 방지하기 때문에 무한 루프를 효과적으로 생성한다.

 

퀵 정렬

quick_sort([]) -> [];
quick_sort([Pivot|Rest]) ->
  quick_sort([X || X <- Rest, X < Pivot])
  ++ [Pivot] ++
    quick_sort([X || X <- Rest, X >= Pivot]).

기존에는 다음과 같이 해결할 수 있었다. 이 경우에 한 가지 문제점은 꼬리재귀를 이용하지 않고, 각각을 여러 번 순회해야 한다는 것이다. 

tail_quick_sort(L) ->
  [H|_] = L,
  Left = tail_quick_left_sort(L, []),
  Right = tail_quick_right_sort(L,[]),
  Left ++ tail_reverse(Right) -- [H].

tail_quick_left_sort([], List) -> List;
tail_quick_left_sort([Pivot|T],List) -> tail_quick_left_sort([X || X <- T, X < Pivot], [Pivot | List]).

tail_quick_right_sort([], List) -> List;
tail_quick_right_sort([Pivot|T],List) -> tail_quick_right_sort([X || X <- T, X >= Pivot], [Pivot | List]).

꼬리 재귀를 이용하면 다음과 같이 짤 수도 있다. 마지막에 한번 빼야하는 곳에서 문제가 발생할 수는 있지만 꼬리 재귀를 이용했다는 점과 딱 한번만 저 연산을 이용하면 된다는 점 때문에 첫번째 방식보단 괜찮을 수도 있다. 

tail_quick_sort([]) -> [];
tail_quick_sort([Pivot|Rest]) ->
  {Smaller, Larger} = partition(Pivot, Rest, [], []),
  tail_quick_sort(Smaller) ++ Pivot ++ tail_quick_sort(Larger).


partition(_, [], Smaller, Larger) -> {Smaller, Larger};
partition(Pivot, [H|T], Smaller, Larger) ->
  if
    H =< Pivot -> partition(Pivot, T, [H|Smaller], Larger);
    H > Pivot -> partition(Pivot, T, Smaller, [H|Larger])
  end .

두번째 방법은 정렬해야 할 대상을 파티셔닝 할 때 꼬리재귀를 이용하는 방식이다. 꼬리재귀를 이용해서 Pivot보다 작고 큰 녀석을 각각 구하고 재귀를 돌려버리는 방식이다. 

 

트리로 접근하기

 

 

 

재귀적으로 생각하기

재귀적으로 생각하는 것은 모든 것을 잘게 쪼개서 세분화한다. 그리고 이 세분화 한 것들을 합쳐서 정답으로 만드는 과정이 재귀다. 오히려 얼랭에서 이런 재귀는 좀 더 명확하다. 

왜냐하면 "이 조건이 들어오면 이런 일을 하세요"라는 것인데, 이미 함수 헤더와 패턴 매칭을 하게 되므로 이 과정은 더욱 더 정확하게 볼 수 있다.

 

 

 

 

 

 

 

 

https://learnyousomeerlang.com/recursion