재귀 (컴퓨터 과학)

컴퓨터 과학에 있어서 재귀(再歸, recursion)는 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻하며, 이를 프로그래밍에 적용한 재귀 호출(recursive call)의 형태로 많이 사용된다. 또 사진이나 그림 등에서 재귀의 형태를 사용하는 경우도 있다.

예시

계승 
계승을 구하는 법은 재귀가 가장 많이 이용되는 예의 하나이다. 예컨대, C로 계승을 구하는 방법은 다음 코드와 같다.

C 
 unsigned int factorial(unsigned int n)
 {
     if (n <= 1)
         return 1;
     else
         return n * factorial(n-1);
 }

스칼라 
  def factorial(n: Int): Int = if (n <= 1) 1 else n * factorial(n-1)

이 코드에서는 함수의 값을 반환할 때 그 자신에 n-1의 인자를 넘겨 다시 호출하는 재귀를 사용하고 있다.

같이 보기 
 재귀
 재귀 약자
 꼬리 재귀

재귀
이론 컴퓨터 과학
계산 가능성 이론
함수 (프로그래밍)