Recursion, Tail Recursion

무언가를 반복 처리해야 하는 경우 , Elixir에서는 recursiove 함수를 사용합니다. 

 

for 문이 있기는 하지만, 다른 언어와의 for 문과는 좀 다르게 사용하는  Comprehensions 로 사용됩니다. 

(https://elixirschool.com/ko/lessons/basics/comprehensions/) 

 

다음의 코드는 1부터 주어지는 수까지의 합을 구하는 함수입니다.

	defmodule Recur do
	def sum(1) do
	1
	end
	def sum(n) do
	sum(n-1) + n
	end
	end

view raw recur1.ex hosted with ❤ by GitHub

Recursion과 패턴 매칭으로 구현하였습니다. 

 

동작은 잘 하지만, 위의 코드는 좋지 않은 코드 작성의 예입니다. 

이유는 sum(n-1) + n 부분의 비효율성 때문입니다. 

 

sum(n-1)은 다시 sum을 호출하는데, 이 sum 은 수행이 완료되는 시점에 다시 호출한 원래 sum 함수로 돌아와야 합니다. 

   sum(3)

       -> sum(2)

             -> 1

       -> sum(2)

    sum(3) 

 

n의 값이 작을 경우에야 별 문제가 없겠지만, n 값이 커지면, 함수 호출될 때 다마 호출한 함수로 돌아와야 하게 때문에 많은 스택을 사용해야 합니다. 

 

이 코드는 다음과 같이 작성되어야 합니다. 

	defmodule Recur do
	def sum(1,acc) do
	1 + acc
	end
	def sum(n,acc) do
	acc = acc + n
	sum(n-1,acc)
	end
	def sum(n) do
	sum(n,0)
	end
	end

view raw recur2.ex hosted with ❤ by GitHub

 

앞의 코드와 다른 부분은 

sum(n-1,acc) 로 recursive call이 이루어지는 부분이 함수의 가장 마지막이라는 겁니다. 

 

누적 값은 acc에 계산이 되므로 sum(1, acc)  code에서는 그저 acc + 1을 return 합니다.

sum(1,acc)가 수행되고 나서 바로 return을 하면되며, 이전의 코드 처럼 앞에 호출한 sum 함수로 다시 돌아갈 필요가 없습니다. 

 

이런 식의 recursive call 을 tail recursion이라 합니다. 

 

이런식으로 작성된 코드는  자기 자신을 호출하지만 가장 마지막 라인에서 호출이 되었으므로,  원래 호출한 위치로 돌아오지 않아도 됩니다. 

 

혹시, recursive function을 작성해야 할 필요가 있으실 때는, 꼭 tail recursive 함수로 작성하시기 바랍니다.

그리고, Elixir에서, 기본 제공하는 library 들은 모두 tail recursion으로 작성되어 있습니다. 

 

아래의 Enum.reduce 함수가 대표적인 예입니다. 

 

           Enum.reduce([1, 2, 3], 0, fn x, acc -> x + acc end)

 

여기서 reduce 함수의 두 번째 파라미터가 위의 코드 예와 같이 누적 값이 저장되는 변수가 되며, 누적 값의 초기 값을 0으로 지정한 것입니다.