[프로그래밍 지식] 재귀 함수란?

 재귀 함수(되부름 함수)란 함수 안에서 함수를 호출하는 방식이다.

 

 1~10까지의 합을 구하는 경우를 생각해보자.

 for문은 자신이 혼자 1+2+3+4+5+6+7+8+9+10을 더하는 것이다.

 

 반면 재귀함수는 뒤에 애한테 1~9까지의 합을 물어보고 그 값에 10을 더하는 방식을 반복한다.

 

 하지만 이런 단순 계산은 재귀를 통해 호출하는 것보다 이미 알고 있는 계산식에 대입시켜서 푸는 것이 더 빠르다. 예를 들어 피보나치 수열의 경우에도 점화식, d[i]=d[i-1]+d[i-2]를 통하면 획기적으로 빠른 속도로 처리가 가능한데, 이는 재귀에서 중복되는 값을 계속해서 호출하고 계산하기에 발생하는 문제이다.

 

 하지만 재귀함수는 알고리즘에서 80% 이상이 재귀함수를 기반으로 개량하여 만들어져 BOJ 문제 또는 코딩테스트 어려운 문제를 풀기 위해서는 필수적인 요소라고 볼 수 있다.