재귀 함수란?
함수 안에 자신의 함수를 다시 호출하는 함수를 의미한다. 이러한 재귀함수는 자신의 로직을 내부적으로 반복하다가, 일정한 조건이 만족되면 함수를 이탈하여 결과를 반환한다.
함수안, Java로 치면 메소드 내 구현부에서 다시 자기 자신의 메소드를 반복적으로 호출하는 것을 말한다.
수학에서의 재귀가 허용 되듯, Java는 재귀적 메소드 호출을 허용 한다.
말로는 알겠다. 그런데 어떤 흐름을 가지고 있는지 자세히 살펴보지 못했다. 그리고 알고리즘이 어렵다고 생각했었던 주요 원인 중 하나가 이 재귀 함수를 이해하지 못했었기 때문이다. 이번에 그 흐름을 정확히 파악하고자 한다.
우선 문제는 내가 팩토리얼 함수에 대한 개념을 공부한지 10년이 넘은 것이다. 이해하려면 아주 쉬운 형태로 변형되어야 한다. 기억나는 것은 !5 이런식으로 뭐 표현했었다는것? 이걸 말로만, 글로만 보면 절대 이해가 안된다. 나만 그럴수도 있다.
f(x) = … 처럼 수학적으로 되있는걸 보면 안그래도 머리아픈데 시간 끌릴 것 같아서 바로 Java의 예시를 통해서 이해하려고 몇번이나 반복하면서 살펴봤다.
재귀적(순환적) 메소드에 대해서 흐름을 파란색처럼 생각했었는데, 그리고 다른 강의를 볼 때도 그 때만 그냥 끄덕끄덕 뭐 그런가보다 하고 넘어갔는데 뒤돌아보면 어떤식으로 되는지 까먹기 바빴다.
빨간색 처럼 요청과 반환의 흐름으로 생각해보니 이해하기가 더욱 편해졌다.
최초 메인 메서드로부터 3이란 값이 입력되면 팩토리얼 메소드에서 n은 3을 매개변수로 받고
구현부에서 또 자신의 메소드를 호출하는데 n-1이라는 매개변수를 전달한다.
여기서 흐름을 바로 해당 메소드의 매개변수를 위로 올려다 보지 말고, 첫 메소드를 호출한 부분을 메소드(1)이라고 생각하자. 이후,
또 하나의 가상 메서드가 호출되었다고 생각하고 n-1인 2를 매개변수로 전달하는 팩토리얼 메소드(2가상)를 생각하고 또 구현부의 흐름을 타고 내려가서 n-1가 1인 팩토리얼 메소드(3가상)을 마주치고, 재귀의 끝인 조건 if(n==1)에서 return 1을 만난다.
그럼 역으로 이제 각 가상 메소드를 호출했던 부분에 반환값들이 대입된다. 마지막 메소드(3)을 호출했던 그 위의 메소드(2)에 호출한 부분에 반환값 1이 대입되고, return n * factorial(n-1)을 2*1 이란 값을 위로 반환한다.
그 메소드(2)를 호출 했었던 가장 처음 메소드(1)은 return n*factorial(n-1)이란 부분에서 n은 최초 메인으로부터 전달되었던 3* 메소드(2)의 반환값인 2가 반환되어 결과로 출력되는데, 3*2로 6이 나오게 된다.