맨위로가기

재귀 (컴퓨터 과학)

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

재귀는 함수가 자신을 호출하는 프로그래밍 기법으로, 문제의 하위 문제로 나누어 해결하는 분할 정복 방식에 사용된다. 재귀 함수는 하나 이상의 기저 사례와 재귀 사례를 가지며, 기저 사례는 함수가 직접 결과를 반환하는 경우, 재귀 사례는 함수가 자신을 다시 호출하는 경우를 의미한다. 재귀는 팩토리얼 계산, 최대공약수 계산, 하노이의 탑, 이진 탐색, 연결 리스트, 이진 트리, 파일 시스템 순회 등 다양한 알고리즘과 자료 구조에 활용된다.

재귀는 반복과 표현력이 동등하며, 꼬리 재귀 함수는 컴파일러에 의해 최적화되어 반복과 유사한 성능을 낼 수 있다. 재귀 알고리즘의 시간 복잡도는 점화식과 마스터 정리를 통해 분석할 수 있으며, 재귀 알고리즘은 스택 오버플로우에 취약할 수 있고, 무한 재귀 오류를 발생시킬 수 있다. 논리 프로그래밍에서 재귀는 절차적, 논리적 해석 모두 가능하다.

더 읽어볼만한 페이지

  • 재귀 - 무한 루프
    무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다.
  • 재귀 - 점화식
    점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다.
  • 이론 컴퓨터 과학 - 알고리즘
    알고리즘은 문제 해결을 위한 명확하고 순서화된 유한 개의 규칙 집합으로, 알콰리즈미의 이름에서 유래되었으며, 수학 문제 해결 절차로 사용되다가 컴퓨터 과학에서 중요한 역할을 하며 다양한 방식으로 표현되고 효율성 분석을 통해 평가된다.
  • 이론 컴퓨터 과학 - 자동화된 추론
    자동화된 추론은 컴퓨터 프로그램을 사용하여 논리적 추론을 수행하는 인공지능 분야로, 수리 논리학의 발전과 초기 연구를 통해 자동 정리 증명 분야의 기틀을 마련했으며, AI 겨울을 겪었지만 소프트웨어 검증 등 다양한 분야에 활용되며 Coq, HOL Light 등의 증명 보조기가 개발되어 난제들의 형식적 증명에 기여했다.
  • 계산 가능성 이론 - 처치-튜링 논제
    처치-튜링 논제는 모든 효과적인 계산 과정이 튜링 기계로 수행될 수 있다는 가설로, 알고리즘과 계산 가능성의 본질에 대한 논의를 촉발하며 컴퓨터 과학과 철학 분야에서 활발히 연구되고 있다.
  • 계산 가능성 이론 - 튜링 기계
    튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
재귀 (컴퓨터 과학)
재귀 (컴퓨터 과학)
M.C. 에셔의 그림 그리는 손. 재귀적 프로세스의 예시이다.
M.C. 에셔의 그림 그리는 손. 재귀적 프로세스의 예시이다.
개요
종류직접 재귀
간접 재귀
관련 개념재귀적 정의
수학적 귀납법
프랙탈
되추적
코루틴
함수형 프로그래밍
무한 루프

2. 재귀 함수와 알고리즘

계승은 재귀가 많이 사용되는 예시 중 하나이다. C로 계승을 구하는 방법은 다음과 같다.



unsigned int factorial(unsigned int n)

{

if (n <= 1)

return 1;

else

return n * factorial(n-1);

}



이 코드에서 함수는 값을 반환할 때 자신을 다시 호출하는 재귀를 사용한다.

일반적인 알고리즘 설계 기법은 문제를 원래 문제와 같은 유형의 하위 문제로 나누고, 하위 문제를 해결한 다음, 그 결과들을 합치는 것이다. 이러한 방식을 분할 정복 방식이라고 한다. 동적 프로그래밍 또는 메모이제이션은 이전에 해결된 하위 문제의 결과를 룩업 테이블에 저장하여 반복적으로 해결하는 것을 피하고 계산 시간을 절약하는 방법이다.

2. 1. 기저 사례

재귀 함수 정의는 하나 이상의 ''기저 사례''를 가지는데, 이는 함수가 자명하게 (재귀 없이) 결과를 생성하는 입력값이며, 하나 이상의 ''재귀 사례''를 갖는데, 이는 프로그램이 재귀하는 (자신을 호출하는) 입력값이다. 예를 들어, 팩토리얼 함수는 0! = 1영어과, 모든 ''n'' > 0영어에 대해 ''n''! = ''n''(''n'' − 1)!영어와 같은 식으로 재귀적으로 정의할 수 있다. 어느 쪽 방정식도 그 자체로는 완전한 정의를 구성하지 않는다. 첫 번째는 기저 사례이고, 두 번째는 재귀 사례이다. 기저 사례는 재귀의 사슬을 끊기 때문에 "종료 사례"라고도 한다.

재귀 사례의 역할은 복잡한 입력을 더 간단한 입력으로 분해하는 것으로 볼 수 있다. 제대로 설계된 재귀 함수에서 각 재귀 호출 시 입력 문제는 결국 기저 사례에 도달하도록 단순화되어야 한다. (정상적인 상황에서 종료되지 않도록 설계된 함수, 예를 들어 일부 시스템 및 서버 프로세스는 이에 대한 예외이다.) 기저 사례를 작성하지 않거나 잘못 테스트하면 무한 루프가 발생할 수 있다.

일부 함수(예: ''e'' = 1/0! + 1/1! + 1/2! + 1/3! + ...영어의 수열을 계산하는 함수)의 경우 입력 데이터에 의해 암시되는 명확한 기저 사례가 없다. 이러한 경우 매개변수 (예: 우리 수열 예제에서 더할 항의 개수)를 추가하여 기저 사례를 설정하는 '중지 기준'을 제공할 수 있다. 이러한 예는 코재귀에 의해 더 자연스럽게 처리되며, 여기서 출력의 연속된 항은 부분 합이다. 이는 "''n''번째 항(''n''번째 부분 합)을 계산하라"고 말하는 인덱싱 매개변수를 사용하여 재귀로 변환할 수 있다.

2. 2. 재귀 사례

계승 (수학)을 구하는 것은 재귀가 많이 사용되는 예시 중 하나이다. 예를 들어, C로 계승을 구하는 방법은 특정 코드로 구현할 수 있다.

일반적인 알고리즘 설계 방법은 문제를 원래 문제와 같은 유형의 하위 문제로 나누고, 하위 문제를 해결한 다음 결과를 합치는 것이다. 이를 분할 정복 방식이라고 한다. 이전에 해결된 하위 문제의 결과를 룩업 테이블에 저장하여 반복적인 해결을 피하고 계산 시간을 절약하는 방법을 동적 프로그래밍 또는 메모이제이션이라고 한다.

재귀 함수 정의는 하나 이상의 '''기저 사례'''를 가진다. 기저 사례는 함수가 재귀 없이 결과를 바로 생성하는 입력값이다. 또한, 하나 이상의 '''재귀 사례'''를 가지는데, 이는 프로그램이 자기 자신을 호출하는 입력값이다. 예를 들어, 팩토리얼 함수는 0! = 1 (기저 사례)과 n > 0 인 모든 n에 대해 n! = n(n - 1)! (재귀 사례)와 같이 재귀적으로 정의할 수 있다. 기저 사례는 재귀의 사슬을 끊기 때문에 "종료 사례"라고도 한다.

재귀 사례는 복잡한 입력을 더 간단한 입력으로 분해하는 역할을 한다. 제대로 설계된 재귀 함수에서는 각 재귀 호출 시 입력 문제가 단순화되어 결국 기저 사례에 도달해야 한다. (일부 시스템 및 서버 프로세스처럼 정상적인 상황에서 종료되지 않도록 설계된 함수는 예외이다.) 기저 사례를 작성하지 않거나 잘못 테스트하면 무한 루프가 발생할 수 있다.

e|e영어 = 1/0! + 1/1! + 1/2! + 1/3! + ... 의 수열을 계산하는 함수처럼, 입력 데이터에 의해 암시되는 명확한 기저 사례가 없는 경우도 있다. 이럴 때는 매개변수 (예: 수열 예제에서 더할 항의 개수)를 추가하여 기저 사례를 설정하는 '중지 기준'을 제공할 수 있다. 이러한 예는 코재귀로 더 자연스럽게 처리할 수 있으며, 출력의 연속된 항은 부분 합이다. 이는 "n번째 항(n번째 부분 합)을 계산하라"고 말하는 인덱싱 매개변수를 사용하여 재귀로 변환할 수 있다.

2. 3. 재귀적 자료형

많은 컴퓨터 프로그램은 임의로 많은 양의 데이터를 처리하거나 생성해야 한다. 재귀는 프로그래머에게 정확한 크기를 알 수 없는 데이터를 표현하는 기술이다. 프로그래머는 이 데이터를 자기 참조 정의로 지정할 수 있다. 자기 참조 정의에는 귀납적 정의와 상호 귀납적 정의의 두 가지 유형이 있다.

2. 4. 귀납적으로 정의된 데이터

귀납적으로 정의된 재귀적 자료 정의는 데이터의 인스턴스를 구성하는 방법을 지정하는 정의이다. 예를 들어, 연결 리스트는 귀납적으로 정의할 수 있다. (여기서는 Haskell 구문 사용):

```haskell

data ListOfStrings = EmptyList | Cons String ListOfStrings

```

위 코드는 문자열의 리스트가 비어 있거나, 문자열과 문자열 리스트를 포함하는 구조체임을 지정한다. 정의에 있는 자기 참조는 임의의 (유한한) 수의 문자열 리스트 구성을 허용한다.

귀납적 정의의 또 다른 예는 자연수 (또는 양의 정수)이다:

```text

자연수는 1 또는 n+1이며, 여기서 n은 자연수이다.

```

마찬가지로 재귀적 정의는 프로그래밍 언어에서 식과 문의 구조를 모델링하는 데 자주 사용된다. 언어 설계자는 종종 바커스-나우르 표기법과 같은 구문을 사용하여 문법을 표현한다. 다음은 곱셈과 덧셈이 있는 간단한 산술 표현식 언어에 대한 그러한 문법이다:

```bnf

::=

| ( * )

| ( + )

```

이것은 표현식이 숫자, 두 표현식의 곱 또는 두 표현식의 합임을 나타낸다. 두 번째 및 세 번째 줄에서 표현식을 재귀적으로 참조함으로써, 문법은 `(5 * ((3 * 6) + 8))`와 같이 단일 표현식에 여러 개의 곱셈 또는 덧셈 연산이 있는 임의로 복잡한 산술 표현식을 허용한다.

2. 5. 상호 귀납적으로 정의된 데이터와 코재귀

코귀납적 데이터 정의는 데이터 조각에 대해 수행될 수 있는 연산을 지정하는 정의이다. 일반적으로 자기 참조적 코귀납적 정의는 무한 크기의 데이터 구조에 사용된다.

문자열의 무한 스트림에 대한 코귀납적 정의는 비공식적으로 다음과 같다.

  • 문자열 스트림은 다음과 같은 객체 s이다.
  • * head(s)는 문자열이고,
  • * tail(s)는 문자열 스트림이다.


이는 문자열 리스트에 대한 귀납적 정의와 매우 유사하다. 차이점은 이 정의가 데이터 구조의 내용에 접근하는 방법, 즉 `head` 및 `tail` 접근자 함수를 통해 접근하는 방법과 해당 내용이 무엇일 수 있는지를 지정하는 반면, 귀납적 정의는 구조를 생성하는 방법과 구조를 생성할 수 있는 대상을 지정한다는 것이다.

코재귀는 코귀납과 관련이 있으며, (가능성이 있는) 무한 객체의 특정 인스턴스를 계산하는 데 사용할 수 있다. 프로그래밍 기술로서, 이는 대부분 지연 프로그래밍 언어의 맥락에서 사용되며, 프로그램의 출력의 원하는 크기 또는 정밀도를 알 수 없는 경우 재귀보다 선호될 수 있다. 이러한 경우 프로그램은 무한히 크거나 무한히 정밀한 결과에 대한 정의와 해당 결과의 유한한 부분을 가져오는 메커니즘이 모두 필요하다. 처음 n개의 소수를 계산하는 문제는 코재귀 프로그램으로 해결할 수 있다.

2. 6. 단일 재귀와 다중 재귀

자기 참조를 한 번만 하는 재귀는 '''단일 재귀'''라고 하고, 여러 번 하는 재귀는 '''다중 재귀'''라고 한다. 단일 재귀의 일반적인 예로는 선형 검색과 같은 목록 순회나 팩토리얼 함수 계산이 있다. 다중 재귀의 일반적인 예로는 깊이 우선 탐색과 같은 트리 순회가 있다.

단일 재귀는 다중 재귀보다 훨씬 효율적인 경우가 많으며, 일반적으로 선형 시간으로 실행되고 고정 공간을 필요로 하는 반복 계산으로 대체될 수 있다. 반면 다중 재귀는 지수 시간과 공간을 필요로 할 수 있으며, 명시적인 스택 없이는 반복으로 대체될 수 없으므로 더 근본적으로 재귀적이다.

다중 재귀는 때때로 단일 재귀로 변환될 수 있으며, 필요하다면 반복으로도 변환될 수 있다. 예를 들어, 피보나치 수를 단순하게 계산하는 것은 각 값이 두 개의 이전 값을 필요로 하므로 다중 반복을 수반하지만, 두 개의 연속적인 값을 매개변수로 전달하여 단일 재귀로 계산할 수 있다. 이는 초기 값에서부터 구축하고 각 단계에서 두 개의 연속적인 값을 추적하는 코어귀환으로 더 자연스럽게 구성된다. 더 정교한 예로는 스레드 이진 트리를 사용하여 다중 재귀 대신 반복적인 트리 순회를 허용하는 것이 있다.

2. 7. 간접 재귀

간접 재귀는 함수가 직접 자신을 호출하는 대신, 다른 함수를 통해 간접적으로 자신을 호출하는 방식이다. 예를 들어 함수 ''f''가 자신을 직접 호출하는 대신 함수 ''g''를 호출하고, ''g''가 다시 ''f''를 호출하는 경우가 이에 해당한다. 이러한 방식은 세 개 이상의 함수가 연쇄적으로 호출되는 경우에도 적용될 수 있다. 예를 들어 함수 1이 함수 2를 호출, 함수 2가 함수 3을 호출, 함수 3이 다시 함수 1을 호출하는 순환 구조도 간접 재귀의 한 형태이다.

간접 재귀는 상호 재귀라고도 불리는데, 이는 좀 더 대칭적인 관점을 강조하는 용어이다. 예를 들어 ''f''가 ''g''를 호출하고, ''g''가 다시 ''f''를 호출하는 상황에서 ''f''의 관점에서는 ''f''가 간접 재귀를 하는 것이고, ''g''의 관점에서도 마찬가지이다. ''f''와 ''g'' 모두의 관점에서는 서로 상호 재귀를 하는 것이다. 이와 같이 서로를 호출하는 세 개 이상의 함수 집합을 상호 재귀 함수 집합이라고 한다.

2. 8. 익명 재귀

재귀는 일반적으로 함수를 이름으로 명시적으로 호출하여 수행된다. 그러나 재귀는 현재 문맥을 기반으로 함수를 암시적으로 호출하여 수행할 수도 있으며, 이는 특히 익명 함수에 유용하며, 익명 재귀라고 한다.

2. 9. 구조적 재귀와 생성적 재귀

구조적 재귀는 입력 데이터의 구조를 따라 재귀 호출이 이루어지는 방식이다. 각 재귀 호출에 대한 인수는 원래 입력의 필드 내용이다.[6] 구조적 재귀는 XML 처리, 이진 트리 생성 및 검색 등 거의 모든 트리 순회를 포함한다. 팩토리얼과 같은 함수도 자연수의 대수적 구조를 고려하여 구조적 재귀로 간주할 수 있다.

생성적 재귀는 주어진 데이터로부터 완전히 새로운 데이터를 생성하고 이를 사용하여 재귀하는 방식이다.[7] 생성적 재귀의 예로는 최대공약수, 퀵 정렬, 이진 탐색, 병합 정렬, 뉴턴의 방법, 프랙탈, 적응적 적분 등이 있다.

구조적 재귀 함수는 각 재귀 호출이 더 작은 입력 데이터를 받으므로 구조적 귀납법을 통해 쉽게 종료됨을 보일 수 있다. 반면, 생성적 재귀 함수는 종료 증명이 더 복잡할 수 있으며, 무한 루프를 피하기 위해 더 많은 주의가 필요하다. 생성적 재귀는 종종 코재귀 함수로 해석될 수 있으며, 각 단계는 새로운 데이터를 생성한다. 이 코재귀를 종료하려면 데이터가 결국 어떤 조건을 만족해야 하는데, 이는 반드시 보장되지 않는다.

3. 구현 문제

실제 구현에서 순수한 재귀 함수(기저 사례에 대한 단일 확인, 그렇지 않으면 재귀 단계) 대신 명확성 또는 효율성을 위해 여러 가지 수정이 이루어질 수 있다. 여기에는 다음이 포함된다.


  • 래퍼 함수(상단)
  • 기저 사례 단락 회로(하단) (일명 "암 길이 재귀")
  • 하이브리드 알고리즘(하단) – 데이터가 충분히 작아지면 다른 알고리즘으로 전환


우아함 측면에서 래퍼 함수는 일반적으로 승인되는 반면, 특히 학계에서는 기저 사례 단락 회로를 좋지 않게 여긴다. 하이브리드 알고리즘은 종종 효율성을 위해 사용되어 작은 경우 재귀 오버헤드를 줄이며, 암 길이 재귀는 이의 특별한 경우이다.[1]

3. 1. 래퍼 함수

래퍼 함수는 직접 호출되지만 스스로 재귀하지 않고, 실제로 재귀를 수행하는 별도의 보조 함수를 호출하는 함수이다.[1]

래퍼 함수는 매개변수의 유효성을 검사하고(따라서 재귀 함수는 이러한 단계를 건너뛸 수 있음), 초기화(메모리 할당, 변수 초기화)를 수행하며, "재귀 수준" 또는 메모이제이션을 위한 부분 계산과 같은 보조 변수에 사용되고, 예외 및 오류를 처리할 수 있다.[1] 중첩 함수를 지원하는 언어에서는 보조 함수가 래퍼 함수 내부에 중첩되어 공유 범위를 사용할 수 있다.[1] 중첩 함수가 없는 경우, 보조 함수는 가능한 경우 별도의 함수로, 비공개로 설정된다(직접 호출되지 않으므로).[1] 정보는 참조 전달을 사용하여 래퍼 함수와 공유된다.[1]

3. 2. 기저 사례 단락 회로

기저 사례 단락 회로(Arm's-length recursion)는 재귀 호출을 하기 *전에* 기저 사례를 확인하는 기법이다. 즉, 다음 함수 호출이 기저 사례인지 확인하여, 해당될 경우 함수를 호출하지 않고 바로 값을 반환한다. 이는 불필요한 함수 호출의 오버헤드를 줄여 효율성을 높이기 위해 사용된다.[8]

예를 들어, 팩토리얼 함수에서 기저 사례는 0! = 1 이다. 일반적인 재귀 함수에서는 1!을 계산하기 위해 0!을 호출하지만, 단락 회로를 사용하면 1!의 값을 바로 반환하여 0!에 대한 불필요한 함수 호출을 방지할 수 있다.

팩토리얼: 일반적인 방식 vs. 단락 회로
일반적인 재귀단락 회로 재귀



위 코드에서 `fac2` 함수는 n=2일 때 2를 바로 반환하여 `fac2(1)` 호출을 방지한다. `fac2wrapper` 함수는 n이 0 또는 1일 때 1을 반환하는 기저 사례를 처리한다.

단락 회로는 특히 트리 탐색과 같이 많은 기저 사례가 있는 경우에 유용하다. 예를 들어, 깊이 우선 탐색에서 현재 노드가 Null인지 확인하는 대신, 현재 노드의 자식이 Null이 아닌 경우에만 재귀 호출을 수행하여 효율성을 높일 수 있다. 이는 함수 호출 횟수를 최대 절반까지 줄일 수 있다.

하지만, 단락 회로는 기저 사례와 재귀 단계의 구분을 모호하게 만들어 코드의 가독성을 떨어뜨릴 수 있다는 단점이 있다.[8]

3. 3. 하이브리드 알고리즘

하이브리드 알고리즘은 작은 경우 재귀의 오버헤드를 줄이기 위해 종종 사용되며, 암 길이 재귀는 이의 특별한 경우이다. 재귀 알고리즘은 반복적인 함수 호출 및 반환의 오버헤드 때문에 작은 데이터에 대해 종종 비효율적이다. 이러한 이유로 재귀 알고리즘의 효율적인 구현은 종종 재귀 알고리즘으로 시작하지만, 입력이 작아지면 다른 알고리즘으로 전환한다. 중요한 예는 병합 정렬이며, 데이터가 충분히 작을 때, 예를 들어 타일 병합 정렬과 같이 비재귀적인 삽입 정렬로 전환하여 구현되는 경우가 많다. 하이브리드 재귀 알고리즘은 팀소트와 같이 하이브리드 병합 정렬/삽입 정렬에서 파생된 알고리즘에서 더욱 개선될 수 있다.

4. 반복과의 비교

재귀와 반복은 표현력이 동등하며, 서로 대체 가능하다. 즉, 재귀 함수는 반복문으로, 반복문은 재귀 함수로 바꿀 수 있다. 어떤 방식을 선택할지는 문제와 사용하는 언어에 따라 달라진다.

명령형 프로그래밍에서는 함수 호출 및 호출 스택 관리의 오버헤드를 피하기 위해 반복을 선호하는 경향이 있지만, 다중 재귀에는 재귀가 일반적으로 사용된다. 반면, 함수형 프로그래밍 언어에서는 꼬리 재귀 최적화를 통해 오버헤드가 거의 발생하지 않으므로 재귀를 선호한다. 반복을 사용하여 알고리즘을 구현하는 것이 쉽지 않은 경우도 있다.

xn = f(n, xn-1)를 xbase에서 정의하여 계산하는 템플릿을 비교하면 다음과 같다.

재귀 함수반복 함수
|



명령형 언어에서는 함수를 정의하는 데 오버헤드가 발생하고, 함수형 언어에서는 누산기 변수 x를 정의하는 데 오버헤드가 발생한다.

예를 들어, 팩토리얼 함수는 C 언어에서 반복문으로 구현할 수 있다.

4. 1. 표현력

재귀와 반복은 표현력이 동등하다. 재귀는 명시적인 호출 스택을 사용하여 반복으로 대체될 수 있으며, 반복은 꼬리 재귀로 대체될 수 있다.[9][10] 어떤 방식을 선호할지는 고려 중인 문제와 사용되는 언어에 따라 다르다. 명령형 프로그래밍에서는 특히 단순한 재귀의 경우, 함수 호출 및 호출 스택 관리에 대한 오버헤드를 피할 수 있으므로 반복을 선호하지만, 재귀는 일반적으로 다중 재귀에 사용된다. 반대로, 함수형 프로그래밍 언어에서는 재귀를 선호하며, 꼬리 재귀 최적화를 통해 오버헤드가 거의 발생하지 않는다. 반복을 사용하여 알고리즘을 구현하는 것이 쉽게 달성되지 않을 수 있다.

xbase에서 정의하여 xn = f(n, xn-1)를 계산하는 템플릿은 다음과 같다.

|



명령형 언어의 경우, 오버헤드는 함수를 정의하는 것이고, 함수형 언어의 경우 오버헤드는 누산기 변수 x를 정의하는 것이다.

예를 들어, 팩토리얼 함수는 C 언어에서 재귀를 통해 인수를 전달하고 값을 반환하는 대신 루프 인덱스 변수와 누산기 변수를 할당하여 반복적으로 구현할 수 있다.

오늘날 사용되는 대부분의 프로그래밍 언어는 재귀 함수와 프로시저의 직접적인 지정을 허용한다. 이러한 함수가 호출되면 프로그램의 런타임 환경은 함수의 다양한 인스턴스를 추적한다(종종 호출 스택을 사용하지만 다른 방법을 사용할 수도 있다). 모든 재귀 함수는 재귀 호출을 반복 제어 구조로 바꾸고 호출 스택을 프로그램에서 명시적으로 관리하는 스택으로 시뮬레이션하여 반복 함수로 변환할 수 있다.[11][12]

반대로, 컴퓨터에서 평가할 수 있는 모든 반복 함수와 프로시저(튜링 완전성 참조)는 재귀 함수로 표현할 수 있다. while 루프 및 for 루프와 같은 반복 제어 구조는 함수형 프로그래밍 언어에서 재귀 형식으로 일상적으로 다시 작성된다. 그러나 실제로 이러한 재작성은 모든 언어의 기능은 아닌 꼬리 호출 제거에 의존한다. C, Java, Python은 꼬리 호출을 포함한 모든 함수 호출이 루프 구조를 사용하는 경우 발생하지 않는 스택 할당을 유발할 수 있는 주목할 만한 주류 언어이다. 이러한 언어에서 재귀 형식으로 다시 작성된 작동하는 반복 프로그램은 호출 스택을 오버플로우시킬 수 있지만, 꼬리 호출 제거는 언어의 사양에 포함되지 않는 기능일 수 있으며, 동일한 언어의 서로 다른 구현은 꼬리 호출 제거 기능이 다를 수 있다.

4. 2. 성능 문제

재귀는 함수 호출 오버헤드로 인해 반복보다 느릴 수 있지만, 꼬리 재귀 최적화를 통해 개선할 수 있다. 명령형 프로그래밍에서는 함수 호출 및 호출 스택 관리 오버헤드를 피하기 위해 반복을 선호하지만, 다중 재귀에는 재귀가 일반적으로 사용된다. 함수형 프로그래밍 언어에서는 꼬리 재귀 최적화를 통해 오버헤드가 거의 발생하지 않아 재귀를 선호한다.[11][12]

C나 자바와 같이 반복적인 루프 구문을 선호하는 언어에서는 재귀 프로그램과 관련된 상당한 시간 및 공간 비용이 발생한다. 이는 스택 관리와 함수 호출의 상대적인 속도 저하 때문이다. 반면, 함수형 프로그래밍 언어에서 함수 호출(특히 꼬리 호출)은 일반적으로 매우 빠른 연산이며, 그 차이는 일반적으로 덜 두드러진다.

"팩토리얼" 예제의 재귀적 구현과 반복적 구현 간의 성능 차이는 사용된 컴파일러에 따라 크게 달라진다. 루프 구문을 선호하는 언어에서는 반복적 버전이 재귀적 버전보다 몇 자릿수나 빠를 수 있다. 함수형 언어에서는 두 구현의 전체 시간 차이가 무시할 수 있을 정도일 수 있다.

4. 3. 스택 공간

재귀 함수가 호출될 때 프로그램의 런타임 환경은 함수의 다양한 인스턴스를 추적하기 위해 호출 스택을 사용하는 경우가 많다.[9][10] 일부 프로그래밍 언어에서는 콜 스택의 최대 크기가 힙에서 사용 가능한 공간보다 훨씬 작기 때문에, 재귀 알고리즘은 반복 알고리즘보다 더 많은 스택 공간을 필요로 하는 경향이 있다. 따라서 이러한 언어들은 스택 버퍼 오버플로우를 피하기 위해 재귀의 깊이에 제한을 두기도 하는데, 파이썬이 대표적인 예이다.[13]

4. 4. 취약성

재귀 알고리즘은 스택 오버플로우 공격에 취약할 수 있다.[14] 일부 악성코드는 프로그램의 호출 스택을 특별히 표적으로 삼아 스택의 본질적인 재귀적 특성을 이용한다.[15] 악성코드가 없더라도 무제한 재귀로 인해 스택 오버플로우가 발생하면 프로그램에 치명적일 수 있으며, 예외 처리 논리가 해당 프로세스가 종료되는 것을 막지 못할 수 있다.[16]

일부 프로그래밍 언어에서 콜 스택의 최대 크기는 힙에서 사용 가능한 공간보다 훨씬 작으며, 재귀 알고리즘은 반복 알고리즘보다 더 많은 스택 공간을 필요로 하는 경향이 있다. 결과적으로, 이러한 언어는 때때로 스택 버퍼 오버플로우를 피하기 위해 재귀의 깊이에 제한을 두기도 한다. 파이썬이 그러한 언어 중 하나이다.[13]

4. 5. 다중 재귀 문제

여러 개의 자기 참조를 포함하는 재귀는 '''다중 재귀'''라고 한다. 다중 재귀의 일반적인 예로는 깊이 우선 탐색과 같은 트리 순회가 있다.

다중 재귀는 지수 시간과 공간을 필요로 할 수 있으며, 명시적인 스택 없이는 반복으로 대체될 수 없으므로 더 근본적으로 재귀적이다.[17] 다중 재귀는 때때로 단일 재귀로 변환될 수 있으며, 필요하다면 반복으로도 변환될 수 있다.

다중 재귀 문제는 추적해야 하는 이전 상태 때문에 본질적으로 재귀적이다. 트리 순회와 깊이 우선 탐색이 그 예시이다. 다른 예로는 퀵 정렬과 같은 분할 정복 알고리즘과 아커만 함수와 같은 함수가 있다. 이러한 모든 알고리즘은 명시적 스택의 도움으로 반복적으로 구현할 수 있지만, 스택을 관리하는 데 필요한 프로그래머의 노력과 결과 프로그램의 복잡성은 반복적 솔루션의 장점을 능가한다고 주장할 수 있다.[17]

4. 6. 재귀 리팩토링

재귀 알고리즘은 비재귀 알고리즘으로 대체할 수 있다.[18] 재귀 알고리즘을 대체하는 한 가지 방법은 스택 메모리 대신 힙 메모리를 사용하여 재귀 알고리즘을 시뮬레이션하는 것이다.[19] 또 다른 방법은 비재귀 방식을 완전히 기반으로 하는 대체 알고리즘을 개발하는 것으로, 이는 어려울 수 있다.[20] 예를 들어, 리치 살츠의 와일드매트 알고리즘[21]과 같은 와일드카드 일치에 대한 재귀 알고리즘이 한때 일반적이었다. 동일한 목적을 위한 비재귀 알고리즘, 예를 들어 크라우스 와일드카드 일치 알고리즘과 같은 알고리즘이 재귀의 단점을 피하기 위해 개발되었으며,[22] 테스트 수집 및 프로파일링 성능과 같은 기술을 기반으로 점진적으로 개선되었다.[23]

5. 꼬리 재귀 함수

꼬리 재귀 함수는 모든 재귀 호출이 꼬리 호출이므로 지연된 연산을 구축하지 않는 함수이다. 예를 들어, 아래 표에 제시된 gcd 함수는 꼬리 재귀적이다. 반면, 팩토리얼 함수는 재귀 호출이 꼬리 위치에 있지 않기 때문에 꼬리 재귀적이지 않다. 팩토리얼 함수는 최종 재귀 호출이 완료된 후 수행해야 하는 지연된 곱셈 연산을 구축한다. 컴파일러 또는 인터프리터가 꼬리 재귀 호출을 함수 호출이 아닌 점프로 처리하는 경우, gcd와 같은 꼬리 재귀 함수는 상수 공간을 사용하여 실행된다. 따라서 프로그램은 본질적으로 반복적이며 "for" 및 "while" 루프와 같은 명령형 언어 제어 구조를 사용하는 것과 같다.

꼬리 재귀:재귀 증가:



꼬리 재귀의 중요성은 꼬리 재귀 호출(또는 모든 꼬리 호출)을 수행할 때 호출자의 반환 위치를 호출 스택에 저장할 필요가 없다는 것이다. 재귀 호출이 반환되면 이전에 저장된 반환 위치로 직접 분기된다. 따라서 꼬리 호출의 이러한 속성을 인식하는 언어에서는 꼬리 재귀가 공간과 시간을 절약한다.

6. 실행 순서

함수가 자체적으로 한 번만 호출하는 경우, 재귀 호출 앞에 배치된 명령은 재귀 호출 전에 재귀 호출당 한 번씩 실행된다. 재귀 호출 뒤에 배치된 명령은 최대 재귀에 도달한 후 반복적으로 실행된다.[1]

또한 함수와 구문이 호출 스택에 저장되는 방식 때문에 print 문의 ''순서''가 반전된다는 점에 유의해야 한다.[1]

다음은 C 언어 예시이다.
예시 1

재귀 함수 예시 1


```c

void recursiveFunction(int num) {

printf("%d\n", num);

if (num < 4)

recursiveFunction(num + 1);

}

```
예시 2
재귀 함수 예시 2


```c

void recursiveFunction(int num) {

if (num < 4)

recursiveFunction(num + 1);

printf("%d\n", num);

}

```

함수 2의 출력은 함수 1의 코드에서 `printf` 함수의 위치를 바꾼 것과 같다.

7. 재귀적 절차

재귀적 절차는 자기 자신을 호출하는 절차이다.

계승을 구하는 것은 재귀가 많이 사용되는 예 중 하나이다. 다음은 C로 작성된 계승 함수의 예시이다.

```c

unsigned int factorial(unsigned int n)

{

if (n <= 1)

return 1;

else

return n * factorial(n-1);

}

```

이 코드는 함수 값을 반환할 때 자신을 다시 호출하며, n-1을 인자로 넘긴다. 재귀 함수는 하나 이상의 ''기저 사례''(입력값이 자명하여 재귀 없이 결과를 낼 수 있는 경우)와 하나 이상의 ''재귀 사례''(자신을 다시 호출하는 경우)를 가진다. 팩토리얼 함수는 0! = 1 (기저 사례)과, 모든 n > 0 에 대해 n! = n(n − 1)! (재귀 사례)로 재귀적으로 정의된다. 기저 사례는 재귀의 사슬을 끊기 때문에 "종료 사례"라고도 한다.

재귀 사례는 복잡한 입력을 더 간단하게 분해하는 역할을 한다. 잘 설계된 재귀 함수에서는 각 재귀 호출마다 입력 문제가 단순화되어 결국 기저 사례에 도달해야 한다.

유클리드 호제법은 두 정수의 최대공약수를 계산하는 방법이며, 재귀적으로 표현할 수 있다.

''함수 정의'':

: \gcd(x,y) =

\begin{cases}

x & \mbox{if } y = 0 \\

\gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\

\end{cases}



최대공약수를 구하는 점화 관계는 다음과 같다. (x \% y는 x / y의 나머지이다.)

:\gcd(x,y) = \gcd(y, x \% y) if y \neq 0

:\gcd(x,0) = x

하노이의 탑


하노이의 탑은 재귀를 사용하여 풀 수 있는 수학적 퍼즐이다.[24][25] 세 개의 기둥에 서로 다른 지름의 원반을 쌓고, 큰 원반을 작은 원반 위에 놓을 수 없다는 규칙 하에 한 번에 하나씩 원반을 다른 기둥으로 옮겨야 한다.

''함수 정의'':

: \operatorname{hanoi}(n) =

\begin{cases}

1 & \mbox{if } n = 1 \\

2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\

\end{cases}



''하노이의 탑 점화식'':

:h_n = 2h_{n-1}+1

:h_1 = 1

이진 탐색은 정렬된 배열에서 특정 값을 찾는 알고리즘으로, 각 재귀 단계마다 배열을 반으로 나눈다. 배열 중간 지점의 값과 찾고자 하는 값을 비교하여 다음 세 가지 중 하나를 수행한다.[1]

  • 값을 찾은 경우: 중간 지점의 인덱스를 반환한다.
  • 중간 지점의 값이 더 큰 경우: 배열의 하위 절반을 대상으로 재귀 호출한다.
  • 중간 지점의 값이 더 작은 경우: 배열의 상위 절반을 대상으로 재귀 호출한다.


이진 탐색은 탐색 범위를 절반씩 줄여나가므로 로그 시간 복잡도를 가진다. 즉, 데이터 크기가 커져도 탐색 시간이 비교적 느리게 증가한다.[1]

7. 1. 팩토리얼

계승 (수학)을 구하는 방법은 재귀가 가장 많이 이용되는 예 중 하나이다. 예를 들어, C로 계승을 구하는 방법은 다음과 같다.



unsigned int factorial(unsigned int n)

{

if (n <= 1)

return 1;

else

return n * factorial(n-1);

}



이 코드에서는 함수의 값을 반환할 때 그 자신에 n-1의 인자를 넘겨 다시 호출하는 재귀를 사용하고 있다. 재귀 함수 정의는 하나 이상의 ''기저 사례''를 갖는데, 이는 함수가 자명하게 (재귀 없이) 결과를 생성하는 입력값이며, 하나 이상의 ''재귀 사례''를 갖는데, 이는 프로그램이 재귀하는 (자신을 호출하는) 입력값이다. 예를 들어, 팩토리얼 함수는 0! = 1 과, 모든 n > 0 에 대해 n! = n(n − 1)! 와 같은 식으로 재귀적으로 정의할 수 있다. 어느 쪽 방정식도 그 자체로는 완전한 정의를 구성하지 않는다. 첫 번째는 기저 사례이고, 두 번째는 재귀 사례이다. 기저 사례는 재귀의 사슬을 끊기 때문에 "종료 사례"라고도 한다.

재귀 사례의 역할은 복잡한 입력을 더 간단한 입력으로 분해하는 것으로 볼 수 있다. 제대로 설계된 재귀 함수에서 각 재귀 호출 시 입력 문제는 결국 기저 사례에 도달하도록 단순화되어야 한다.

자연수의 팩토리얼을 계산하는 데 사용되는 함수의 의사 코드는 다음과 같다.

의사 코드 (재귀):



이 함수는 점화식으로도 작성할 수 있다.

:math>b_n = nb_{n-1}

:math>b_0 = 1

이 점화식의 평가는 위 의사 코드를 평가할 때 수행될 계산을 보여준다.

n = 4에 대한 점화식 계산:


7. 2. 최대공약수

유클리드 호제법은 두 정수의 최대공약수를 계산하는 방법으로, 재귀적으로 표현할 수 있다.

''함수 정의'':

: \gcd(x,y) =

\begin{cases}

x & \mbox{if } y = 0 \\

\gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\

\end{cases}



의사 코드 (재귀)



최대공약수를 구하는 점화 관계는 다음과 같다. 여기서 x \% y는 x / y의 나머지를 뜻한다.

:\gcd(x,y) = \gcd(y, x \% y) if y \neq 0

:\gcd(x,0) = x

x = 27, y = 9일 때 점화 관계 계산:
x = 111, y = 259일 때 점화 관계 계산:



위의 재귀 프로그램은 꼬리 재귀를 사용하며, 이는 반복 알고리즘과 동일하다. 위에 표시된 계산은 꼬리 호출을 제거하는 언어에서 수행되는 평가 단계를 보여준다.

아래는 꼬리 호출을 제거하지 않는 언어에 적합한, 명시적 반복을 사용하는 동일한 알고리즘의 버전이다. 변수 ''x''와 ''y''에 완전히 상태를 유지하고 루핑 구문을 사용함으로써, 이 프로그램은 재귀 호출을 수행하고 호출 스택을 늘리는 것을 피한다.

의사 코드 (반복)



반복 알고리즘은 임시 변수를 필요로 하며, 유클리드 호제법에 대한 지식이 주어지더라도 단순한 관찰만으로 과정을 이해하기가 더 어렵지만, 두 알고리즘은 단계에서 매우 유사하다.

7. 3. 하노이의 탑



하노이의 탑은 재귀를 사용하여 풀 수 있는 수학적 퍼즐이다.[24][25] 세 개의 기둥에 서로 다른 지름의 원반들을 쌓을 수 있는데, 큰 원반은 작은 원반 위에 놓을 수 없다. 한 기둥에 ''n''개의 원반이 쌓여 있을 때, 한 번에 하나씩 원반을 다른 기둥으로 옮겨야 한다. 이때 원반을 옮기는 최소 횟수는 얼마인가?

''함수 정의'':

: \operatorname{hanoi}(n) =

\begin{cases}

1 & \mbox{if } n = 1 \\

2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\

\end{cases}



''하노이의 탑 점화식'':

:h_n = 2h_{n-1}+1

:h_1 = 1

n = 4일 때 점화식 계산 과정



의사 코드 (재귀) 예시:

의사 코드



모든 재귀 함수가 명시적인 해를 가지는 것은 아니지만, 하노이의 탑 수열은 아래와 같이 명시적인 공식으로 나타낼 수 있다.[26]

하노이의 탑 명시적 공식


7. 4. 이진 탐색

이진 탐색 알고리즘은 각 재귀 단계마다 배열을 반으로 나누어 정렬된 배열에서 특정 값을 찾는 방법이다. 우선 배열의 중간 지점을 선택하고, 해당 지점의 값과 찾고자 하는 값을 비교한다. 이 비교 결과에 따라 다음 세 가지 조건 중 하나에 해당하는 작업을 수행한다.[1]

  • 중간 지점에서 값을 찾은 경우: 해당 지점의 인덱스를 반환한다.
  • 중간 지점의 값이 찾고자 하는 값보다 큰 경우: 배열의 하위 절반(시작점부터 중간 지점 - 1)을 대상으로 다시 이진 탐색을 재귀적으로 호출한다.
  • 중간 지점의 값이 찾고자 하는 값보다 작은 경우: 배열의 상위 절반(중간 지점 + 1부터 끝점)을 대상으로 다시 이진 탐색을 재귀적으로 호출한다.


이진 탐색은 각 단계마다 탐색 범위를 절반으로 줄여나가기 때문에 로그 시간 복잡도를 가진다. 즉, 데이터의 크기가 커져도 탐색 시간이 비교적 느리게 증가한다.[1]

C 언어에서의 이진 탐색 구현 예시는 다음과 같다.[1]

```c

int search(int *data, int toFind, int count)

{

return binary_search(data, toFind, 0, count-1);

}

int binary_search(int *data, int toFind, int start, int end)

{

int mid = start + (end - start)/2;

if (start > end)

return -1;

else if (data[mid] == toFind)

return mid;

else if (data[mid] > toFind)

return binary_search(data, toFind, start, mid-1);

else

return binary_search(data, toFind, mid+1, end);

}

8. 재귀적 자료 구조

컴퓨터 과학에서 재귀는 리스트나 트리와 같이 동적으로 크기가 변하는 자료 구조를 정의하는 데 유용하게 사용된다.[27] 이러한 재귀적 자료 구조는 런타임 요구 사항에 따라 이론적으로 무한한 크기로 커질 수 있다. 반면, 정적 배열의 크기는 컴파일 시간에 미리 정해져야 한다.

"재귀 알고리즘은 근본적인 문제나 처리할 데이터가 재귀적 용어로 정의될 때 특히 적합하다."[27]

이 섹션의 예시는 "구조적 재귀"를 보여준다. 이 용어는 재귀 절차가 재귀적으로 정의된 데이터에 대해 작동한다는 사실을 의미한다. 즉, 함수 본문의 재귀는 주어진 복합 값의 즉각적인 일부를 소비한다.[7]

8. 1. 연결 리스트

연결 리스트는 재귀적으로 정의될 수 있는 자료 구조이다. 아래는 연결 리스트 노드 구조체의 C 정의이다. 특히 노드가 자체적으로 어떻게 정의되는지 주목해야 한다. ''struct node''의 "next" 요소는 다른 ''struct node''에 대한 포인터로, 효과적으로 리스트 유형을 생성한다.[27]

```c

struct node

{

int data; // 정수 데이터

struct node *next; // 다른 struct node에 대한 포인터

};

```

''struct node'' 데이터 구조가 재귀적으로 정의되었기 때문에, 이에 대해 작동하는 절차는 자연스럽게 재귀 절차로 구현될 수 있다. 아래에 정의된 ''list_print'' 절차는 리스트가 비어 있을 때까지 (즉, 리스트 포인터가 NULL 값을 가질 때까지) 리스트를 따라 이동한다. 각 노드에 대해 데이터 요소(정수)를 인쇄한다. C 구현에서, ''list_print'' 절차에 의해 리스트는 변경되지 않는다.[7]

```c

void list_print(struct node *list)

{

if (list != NULL) // 기본 사례

{

printf ("%d ", list->data); // 정수 데이터를 인쇄하고 공백을 추가합니다.

list_print (list->next); // 다음 노드에 대한 재귀 호출

}

}

8. 2. 이진 트리

이진 트리의 예시


이진 트리는 각 노드가 왼쪽과 오른쪽 자식 노드를 가리키는 재귀적 자료 구조이다. 연결 리스트의 노드와 마찬가지로 자기 자신을 기준으로 재귀적으로 정의된다. C 언어에서 이진 트리는 다음과 같이 정의할 수 있다.



struct node

{

int data; // 정수 데이터

struct node *left; // 왼쪽 하위 트리에 대한 포인터

struct node *right; // 오른쪽 하위 트리에 대한 포인터

};



위 코드에서 `left`는 왼쪽 하위 트리를, `right`는 오른쪽 하위 트리를 가리킨다. 이진 트리는 두 개의 자기 참조 포인터를 가지므로, 트리 연산에는 두 번의 재귀 호출이 필요할 수 있다.[27]

트리에 대한 연산은 재귀를 사용하여 구현할 수 있다. 예를 들어, 주어진 이진 트리에서 특정 값을 찾는 `tree_contains` 함수는 다음과 같이 구현할 수 있다.



// tree_node에 i가 포함되어 있는지 테스트합니다. 그렇다면 1을 반환하고, 그렇지 않으면 0을 반환합니다.

int tree_contains(struct node *tree_node, int i) {

if (tree_node == NULL)

return 0; // 기본 사례

else if (tree_node->data == i)

return 1;

else

return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);

}



이 함수는 트리가 비어있거나(`tree_node == NULL`) 찾는 값(`i`)이 현재 노드의 데이터와 일치하는 경우를 기본 사례로 처리한다. 그렇지 않은 경우, 왼쪽과 오른쪽 하위 트리에 대해 재귀적으로 함수를 호출하여 값을 찾는다.

이진 트리의 중위 순회를 수행하는 `tree_print` 함수는 다음과 같이 구현할 수 있다.



// 중위 순회:

void tree_print(struct node *tree_node) {

if (tree_node != NULL) { // 기본 사례

tree_print(tree_node->left); // 왼쪽으로 이동

printf("%d ", tree_node->data); // 정수를 출력하고 공백을 추가합니다.

tree_print(tree_node->right); // 오른쪽으로 이동

}

}



이 함수는 트리가 비어있지 않은 경우, 먼저 왼쪽 하위 트리를 순회하고, 현재 노드의 데이터를 출력한 후, 오른쪽 하위 트리를 순회한다.

이진 탐색 트리는 각 노드의 데이터 요소가 정렬된 이진 트리의 특수한 경우이다.

8. 3. 파일 시스템 순회

파일 시스템 내 파일의 수는 가변적이므로, 그 내용을 순회하고 열거하는 실질적인 유일한 방법은 재귀이다.[27] 파일 시스템 순회는 트리 순회와 매우 유사하므로 트리 순회의 개념을 파일 시스템 순회에 적용할 수 있다. 아래 코드는 파일 시스템의 전위 순회의 예시이다.

```java

import java.io.File;

public class FileSystem {

public static void main(String[] args) {

traverse();

}

/**

  • 파일 시스템 루트를 얻습니다.
  • 재귀적인 파일 시스템 순회를 진행합니다.
  • /

private static void traverse() {

File[] fs = File.listRoots();

for (int i = 0; i < fs.length; i++) {

System.out.println(fs[i]);

if (fs[i].isDirectory() && fs[i].canRead()) {

rtraverse(fs[i]);

}

}

}

/**

  • 주어진 디렉토리를 재귀적으로 순회합니다.

  • @param fd 순회의 시작점을 나타냅니다.
  • /

private static void rtraverse(File fd) {

File[] fss = fd.listFiles();

for (int i = 0; i < fss.length; i++) {

System.out.println(fss[i]);

if (fss[i].isDirectory() && fss[i].canRead()) {

rtraverse(fss[i]);

}

}

}

}

```

이 코드는 재귀와 반복을 모두 사용한다. 파일과 디렉토리는 반복적으로 처리되며, 각 디렉토리는 재귀적으로 열린다. "rtraverse" 메서드는 직접 재귀의 예시이며, "traverse" 메서드는 래퍼 함수이다. "기저 사례" 시나리오는 주어진 파일 시스템 내에 항상 고정된 수의 파일 및/또는 디렉토리가 있다는 것이다.

9. 재귀 알고리즘의 시간 효율성

일반적인 알고리즘 설계 방법은 문제를 원래 문제와 같은 유형의 하위 문제로 나누고, 하위 문제를 해결한 다음 결과를 합치는 것이다. 이를 분할 정복 방식이라고 한다. 이전에 해결된 하위 문제의 결과를 룩업 테이블에 저장하여 반복 해결을 피하고 계산 시간을 절약하는 방법을 동적 프로그래밍 또는 메모이제이션이라고 한다.

C나 자바처럼 반복문을 선호하는 언어에서는 재귀 프로그램이 스택 관리 오버헤드와 함수 호출 속도 저하로 인해 시간 및 공간 비용이 많이 발생한다. 반면 함수형 프로그래밍 언어에서는 함수 호출, 특히 꼬리 재귀는 매우 빠른 연산이므로 그 차이가 덜하다.

"팩토리얼" 예제의 재귀적 구현과 반복적 구현 간 성능 차이는 컴파일러에 따라 크게 달라진다. 반복문을 선호하는 언어에서는 반복적 버전이 재귀적 버전보다 몇 자릿수나 빠를 수 있다. 함수형 언어에서는 두 구현의 시간 차이가 미미할 수 있다. 실제로 더 큰 숫자를 먼저 곱하는 데 드는 비용이 반복을 통해 절약되는 시간을 압도할 수 있다.

재귀 알고리즘의 시간 복잡도는 점화식으로 표현할 수 있으며, 마스터 정리를 통해 빅 오 표기법으로 나타낼 수 있다.

9. 1. 마스터 정리

재귀 알고리즘의 시간 복잡도는 점화식으로 나타낼 수 있으며, 이는 빅 오 표기법으로 표현된다. 이러한 점화식은 (일반적으로) 하나의 빅 오 항으로 단순화될 수 있다.

함수의 시간 복잡도가 다음 형식일 경우,

: ''T''(''n'') = ''a'' ⋅ ''T''(''n'' / ''b'') + ''f''(''n'')

시간 복잡도의 빅 오 표기법은 다음과 같다.

  • 만약 어떤 상수 ''ε'' > 0에 대해 ''f''(''n'') = O(''n''log''b'' ''a'' - ''ε'')이면, ''T''(''n'') = Θ(''n''log''b'' ''a'')
  • 만약 ''f''(''n'') = Θ(''n''log''b'' ''a'')이면, ''T''(''n'') = Θ(''n''log''b'' ''a'' log ''n'')
  • 만약 어떤 상수 ''ε'' > 0에 대해 ''f''(''n'') = Ω(''n''log''b'' ''a'' + ''ε'')이고, 어떤 상수 ''c'' < 1와 충분히 큰 모든 ''n''에 대해 ''a'' ⋅ ''f''(''n'' / ''b'') ≤ ''c'' ⋅ ''f''(''n'')이면, ''T''(''n'') = Θ(''f''(''n''))


여기서 ''a''는 재귀 호출의 각 레벨에서 재귀 호출의 수를 나타내고, ''b''는 다음 재귀 레벨에서 입력이 얼마나 작아지는지(즉, 문제를 분할하는 조각의 수)를 나타내며, ''f''(''n'')은 각 재귀 레벨에서 재귀와 독립적으로 함수가 수행하는 작업(예: 분할, 재결합)을 나타낸다.

10. 논리 프로그래밍에서의 재귀

논리 프로그래밍에서 재귀는 절차적 해석과 논리적 해석으로 이해될 수 있다.

논리 프로그래밍의 절차적 해석에서, `A :- B` 형태의 절(또는 규칙)은 `A` 형태의 목표를 `B` 형태의 하위 목표로 축소하는 절차로 취급된다. 예를 들어, 프롤로그 절은 다음과 같다.

```prolog

path(X,Y) :- arc(X,Y).

path(X,Y) :- arc(X,Z), path(Z,Y).

```

이 절차는 ''X''에서 ''Y''까지의 경로를 검색하는 데 사용될 수 있으며, ''X''에서 ''Y''까지의 직접적인 아크를 찾거나, ''X''에서 ''Z''까지의 아크를 찾은 다음 ''Z''에서 ''Y''까지의 경로를 재귀적으로 검색하여 찾을 수 있다. 프롤로그는 상향식(또는 후진)으로 추론하고 가능한 경로 공간을 깊이 우선 방식으로 한 번에 한 분기씩 검색하여 이 절차를 실행한다. ''Z''에서 ''Y''까지의 경로를 유한하게 찾지 못하면, 백트래킹하여 ''X''에서 다른 노드로의 아크를 찾으려고 시도한 다음, 다른 노드에서 ''Y''까지의 경로를 검색한다.

그러나 논리 프로그램의 논리적 해석에서 절은 선언적으로 전체적으로 정량화된 조건으로 이해된다. 예를 들어, 경로 찾기 절차의 재귀 절은 모든 ''X'', ''Y'' 및 ''Z''에 대해 ''X''에서 ''Z''까지의 아크와 ''Z''에서 ''Y''까지의 경로가 있으면 ''X''에서 ''Y''까지의 경로가 있다는 지식을 표현하는 것으로 이해된다. 기호 형식으로 표현하면 다음과 같다.

:\forall X, Y, Z(arc(X,Z)\land path(Z,Y) \rightarrow path(X,Y)).

논리적 해석을 통해 독자는 문제를 해결하기 위해 절이 어떻게 사용되는지 알 필요가 없다. 이 절은 프롤로그에서처럼 문제를 하위 문제로 줄이기 위해 상향식으로 사용할 수 있다. 또는 데이터로그에서처럼 조건으로부터 결론을 도출하기 위해 하향식(또는 전진)으로 사용할 수 있다. 이러한 관심사 분리는 추상화의 한 형태로, 선언적 지식을 문제 해결 방법과 분리한다(알고리즘#알고리즘 = 논리 + 제어 참조).[28]

11. 무한 재귀

무한 재귀는 재귀 함수가 종료되지 않고 무한히 호출되는 현상이다. 프로그래머가 재귀 함수를 설계할 때 기저 사례(종료 조건)를 생략하거나 잘못 설정하면 발생한다. 이론적으로 무한 재귀 함수는 영원히 실행되어야 하지만, 실제로는 프로그램이 사용할 수 있는 스택 공간이 제한되어 있기 때문에 결국 스택 오버플로 오류를 발생시키고 프로그램이 중단된다.[29]

다음은 무한 재귀를 발생시키는 자바 코드 예시이다.

```java

public class InfiniteRecursion {

static void recursive() { // 탈출구가 없는 재귀 함수

recursive();

}

public static void main(String[] args) {

recursive(); // 런타임 시 재귀 함수 실행

}

}

```

이 코드를 실행하면 스택 오버플로 오류가 발생한다.

참조

[1] 서적 Concrete Mathematics Addison-Wesley 1990
[2] 간행물 Teaching Recursive Thinking using Unplugged Activities http://www.wiete.com[...]
[3] 서적 Discrete Mathematics with Applications https://archive.org/[...] PWS Publishing Company 1995
[4] 서적 Algorithms + Data Structures = Programs https://archive.org/[...] Prentice-Hall 1976
[5] 웹사이트 Functional Programming {{!}} Clojure for the Brave and True https://www.braveclo[...] 2020-10-21
[6] 문서 2001
[7] 서적 Advanced Functional Programming: 4th International School ftp://nozdr.ru/bibli[...] Springer 2002
[8] 서적 Programming Interviews Exposed: Secrets to Landing Your Next Job https://archive.org/[...] Wiley (publisher)|Wiley 2013
[9] 서적 Python Algorithms: Mastering Basic Algorithms in the Python Language https://books.google[...] Apress 2010
[10] 서적 Data Structures and Algorithms in C++ https://books.google[...] Cengage Learning 2012
[11] 웹사이트 The Anatomy of a Loop - A story of scope and control http://www.ccs.neu.e[...] Georgia Institute of Technology 2012-09-03
[12] 웹사이트 The Anatomy of a Loop http://lambda-the-ul[...] Lambda the Ultimate 2012-09-03
[13] 웹사이트 27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation https://docs.python.[...] Docs.python.org 2012-09-03
[14] 간행물 Matching Wildcards: An Empirical Way to Tame an Algorithm http://www.drdobbs.c[...] 2014
[15] 간행물 Anatomy of a Stack Smashing Attack and How GCC Prevents It http://www.drdobbs.c[...] 2012
[16] 웹사이트 StackOverflowException Class https://msdn.microso[...] Microsoft Developer Network 2018
[17] 웹사이트 Depth First Search (DFS): Iterative and Recursive Implementation http://www.techiedel[...] Techie Delight 2018
[18] 웹사이트 Replace Recursion with Iteration https://www.refactor[...] ThoughtWorks
[19] 웹사이트 How to replace recursive functions using stack and while-loop to avoid the stack-overflow https://www.codeproj[...] CodeProject 2015
[20] 웹사이트 Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick http://blog.moertel.[...] 2013
[21] 웹사이트 wildmat.c https://github.com/t[...] GitHub 1991
[22] 간행물 Matching Wildcards: An Algorithm http://www.drdobbs.c[...] 2008
[23] 웹사이트 Matching Wildcards: An Improved Algorithm for Big Data http://www.developfo[...] Develop for Performance 2018
[24] 문서 1990
[25] 문서 1995
[26] 문서 1995
[27] 문서 1976
[28] 서적 Artificial Intelligence: A Modern Approach §9.3, §9.4 Pearson
[29] 웹사이트 4.8. Infinite Recursion https://runestone.ac[...]


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com