재귀 함수
재귀함수란, 함수가 자기 자신을 호출하는 함수를 말합니다.
이것은 수학적인 개념인 "재귀적 정의" 프로그래밍에 적용한 것입니다.
재귀함수는 종종 반복문으로 구현할 수 있는 문제들을 간단하게 해결할 수 있도록 도와줍니다.
간단한 예를 들어보면, 1부터 n까지의 합을 구하는 함수를 생각해봅시다.
반복문으로는 다음과 같이 구현할 수 있습니다.
int sum(int n) {
int result = 0;
for (int i = 1; i <= n; i++) {
result += i;
}
return result;
}
그러나 재귀함수로는 다음과 같이 구현할 수 있습니다.
int sum(int n) {
if (n == 1) {
return 1;
} else {
return n + sum(n-1);
}
}
위 코드에서 'sum' 함수는 자기 자신을 호출하면서 'n' 부터 1까지의 합을 구합니다.
종료 조건으로 'n'이 1일 때 1을 반환하도록 설정하였습니다.
따라서 'sum(3)'을 호출하면 다음과 같이 동작하게 됩니다.
sum(3)
= 3 + sum(2)
= 3 + (2 + sum(1))
= 3 + (2 + 1)
= 6즉, 'sum(3)'은 1부터 3까지의 합인 6을 반환하게 됩니다.
이처럼 재귀함수는 자기 자신을 호출하면서 종료조건에 도달하면 그 값을 반환합니다.
일반적으로 반복문을 사용하여 문제를 해결할 수 있지만, 경우에 따라 재귀함수를 사용하면 더 간결하고 이해하기 쉬운 코드를 작성할 수 있습니다.
재귀함수는 기본적으로 두 가지 구성 요소로 이루어져 있습니다.
첫 번째는 함수가 자신을 호출하는 부분이고,
두 번째는 종료 조건이 있는 부분입니다.
재귀함수를 작성할 때는 종료 조건을 꼭 명시해야 합니다.
종료 조건이 없으면 함수가 무한히 호출되기 때문에 스택 오버플로우(Stack Overflow)가 발생할 수 있습니다.
재귀함수를 사용하여 문제를 해결할 때는 문제를 작은 부분으로 쪼개서 해결하고,
작은 부분의 해답을 이용하여 큰 문제의 해답을 구하는 방식으로 진행됩니다.
이러한 방식을 분할 정복(Divide and Conquer)이라고 합니다.
예를 들어, 피보나치 수열을 재귀함수를 사용하여 구현한다면, 함수는 자신을 호출하여 이전 두 수의 합을 계산합니다.
이때, 0과 1이라는 두 개의 종료 조건을 사용하여 함수 호출을 멈추게 합니다.
재귀함수의 종류
- 일반적인 재귀 함수
- 함수 내부에서 자신을 호출하는 방식으로 구현되는 일반적인 형태의 재귀 함수입니다.
- 함수 내부에서 자신을 호출하는 방식으로 구현되는 일반적인 형태의 재귀 함수입니다.
- 꼬리 재귀함수
- 함수 호출이 끝나고 나서도 추가적인 작업을 처리하지 않고, 함수 호출 시 넘겨 받은 인자와 함수 내부에서
계산한 결과 값만 반환하는 형태의 재귀 함수입니다. 이 형태의 재귀 함수는 스택 오버플로우 등의
문제를 방지할 수 있습니다.
- 함수 호출이 끝나고 나서도 추가적인 작업을 처리하지 않고, 함수 호출 시 넘겨 받은 인자와 함수 내부에서
- 중첩 재귀함수
- 함수 내부에서 자기 자신을 호출하는 것이 아니라,
다른 함수를 호출하면서 자기 자신을 호출하는 형태의 재귀 함수입니다.
- 함수 내부에서 자기 자신을 호출하는 것이 아니라,
팩토리얼 함수
팩토리얼 함수는 자연수 n에 대해 n! (n 팩토리얼)을 반환하는 함수입니다.
n!은 1부터 n까지의 모든 자연수를 곱한 값이며, 0!은 1로 정의됩니다.
즉, n! = 1 * 2 * 3 * ... * n 입니다.
팩토리얼 함수는 재귀 함수를 이용하여 구현할 수 있습니다.
또한 팩토리얼 함수는 자연수 n에 대해 n!을 계산하는 함수이기 때문에,
주로 수학적 계산이나 조합론적 문제를 풀이하는데 사용됩니다.
실생활에서는 예를 들어, 팩토리얼 함수를 이용하여 주식 시장에서 주식의 증가, 감소를 분석하거나,
인구 증가율을 예측하는 등 수치 데이터를 다룰 때 사용될 수 있습니다.
기술적으로는 알고리즘 구현에서도 많이 사용됩니다.
예를 들어, 퀵 정렬 알고리즘의 평균 시간 복잡도를 계산하는 데에도 팩토리얼 함수가 사용됩니다.
또한, 딥러닝 분야에서는 베이즈 정리의 적용과정에서 연속된 확률 분포를 계산할 때 팩토리얼 함수를 사용합니다.
아래는 팩토리얼 함수를 구현한 C언어 프로그래밍 코드입니다.
#include <stdio.h>
int factorial(int n) {
if (n == 0) { // 종료 조건
return 1;
}
else {
return n * factorial(n - 1); // 자신을 호출하여 문제를 작은 부분으로 쪼개어 해결
}
}
int main() {
int n = 5;
int result = factorial(n);
printf("%d! = %d\n", n, result); // 5! = 120
return 0;
}
* 팩토리얼 함수의 진행 순서 및 세부 설명
| 스택의 상태 | 실행 내용 | 설명 |
| 'factorial(5) | 함수 호출 | |
| 'n = 5' | '5 * factorial(4)' | 자기 자신을 호출하며 ('n-1')로 인수를 넘김 |
| 'n = 5', 'n=4' | '4 * factorial(3)' | 이전 호출의 반환 값('n-1'의 계산 결과)에 'n'을 곱함 |
| 'n = 5', 'n=4', 'n = 3' |
'3 * factorial(2)' | 이전 호출의 반환 값('n-1'의 계산 결과)에 'n'을 곱함 |
| 'n = 5', 'n=4', 'n = 3', 'n=2' |
'2 * factorial(1)' | 이전 호출의 반환 값('n-1'의 계산 결과)에 'n'을 곱함 |
| 'n = 5', 'n=4', 'n = 3', 'n=2', 'n = 1' |
'1 * factorial(0)' | 이전 호출의 반환 값('n-1'의 계산 결과)에 'n'을 곱함 |
| 'n = 5', 'n=4', 'n = 3', 'n=2', 'n = 1', 'n=0' |
1 | 종료 조건에 도달하여 '1'을 반환함 |
| 'n = 5', 'n=4', 'n = 3', 'n=2', |
'2 * 1' | 'factorial(1)'의 반환 값 ('n!')에 'n'을 곱함 |
| 'n = 5', 'n=4', 'n = 3' |
'3 * 2' | 'factorial(2)'의 반환 값 ('n!')에 'n'을 곱함 |
| 'n = 5', 'n=4' | '4 * 6' | 'factorial(3)'의 반환 값 ('n!')에 'n'을 곱함 |
| '5 * 24' | 'factorial(4)'의 반환 값 ('n!')에 'n'을 곱함 | |
| '120' | 'factorial(5)'의 반환 값 ('n!')에 'n'을 곱함 |
위의 표에서 볼 수 있듯이, 재귀 함수가 호출될 때마다 해당 함수의 인수와 지역 변수 등이 스택에 쌓이게 됩니다.
그리고 함수가 종료될 때마다 해당 함수와 관련된 스택 프레임이 제거됩니다.
스택은 함수의 호출 순서와 반대 순서로 제거 되기 때문에,
마지막에 호출된 함수가 가장먼저 종료되고,
처음에 호출된 함수가 가장 마지막에 종료됩니다.
스택프레임(Stack Frame)은 함수 호출 시 생성되는 메모리 공간으로, 해당 함수의 인수, 로컬 변수, 복귀 주소 등이 저장됩니다. 각 함수 호출마다 새로운 스택 프레임이 생성되며, 해당 함수가 종료될 때 스택 프레임은 제거됩니다. 이때 스택 자료 구조를 이용하여 관리되기 때문에, 후입 선출(Last-In-First-Out,LIFO) 구조를 가집니다.
위의 예시에서 'factorial' 함수가 호출될 때마다 해당 함수의 인수 'n'과 지역 변수 등이 새로운 스택 프레임에
저장되며, 함수가 종료될때마다 해당 스택 프레임이 제거 됩니다.
C++
#include <iostream>
int factorial(int n) {
if (n == 0) { // 종료 조건
return 1;
}
else {
return n * factorial(n-1); // 자신을 호출하여 문제를 작은 부분으로 쪼개고 해결
}
}
int main() {
int n = 5;
int result = factorial(n);
std::cout << n << "! = " << result << std::endl; // 5! = 120
return 0;
}
Python
def factorial(n):
if n == 0: # 종료 조건
return 1
else:
return n * factorial(n-1) # 자신을 호출하여 문제를 작은 부분으로 쪼개고 해결
n = 5
result = factorial(n)
print("{}! = {}".format(n, result)) # 5! = 120
피보나치 수열
피보나치 수열은 0과 1로 시작하여, 이전 두 수의 합을 이어서 나열한 수열입니다.
즉. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 과 같이 이어집니다.
피보나치 수열은 실생활에서 여러 곳에서 적용됩니다.
예를 들어, 식물의 잎이나 꽃 잎의 배열, 껍질, 달팽이의 나선형 등에서 피보나치 수열의 형태를 발견할 수 있습니다.
또한 시간, 소리, 빛 등의 자연현상에서도 피보나치 수열의 형태를 발견할 수 있습니다.
또한, 컴퓨터 과학에서도 피보나치 수열은 매우 중요한 역할을 합니다.
예를 들어 재귀 함수를 구현하거나 동적인 프로그래밍 등의 알고리즘에서 피보나치 수열을 사용할 수 있습니다.
또한 피보나치 수열은 연산 속도 측면에서 계산 복잡도가 높아질 수 있어,
알고리즘의 효율성을 검증하는 용도로도 활용됩니다.
또한 피보나치 수열은 무한 수열이며, 골드레이스 비율이라는 수학적 비율에 수렴합니다.
따라서 수학적인 지식을 이해하는 데에도 피보나치 수열이 매우 중요한 역할을 합니다.
아래는 Java 코드를 통해 피보나치 수열을 구하는 함수를 구현한 예제입니다.
public class TestClass{
public static int fibonacci(int n) {
if (n == 0) {
return 0;
}
else if (n == 1) {
return 1;
}
else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
public static void main(String[] args) {
int n = 5;
int result = fibonacci(n);
System.out.println("Fibonacci(" + n + ") = " + result);
}
}
//Fibonacci(5) = 5
* 자바 코드로 구현한 피보나치 수열 함수와 코드 흐름은 다음과 같습니다.
우선, 'fibonacci' 함수가 호출되면 'n'이 0 또는 1인 경우에는 각각 0 또는 1을 반환합니다.
이때, 재귀적으로 호출되는 경우는 'n'이 2이상인 경우입니다.
'n'이 2 이상인 경우에는 'fibonacci(n-1)'과 'fibonacci(n-2)'를 각각 재귀적으로 호출하여 그 값을 더한 후 반환합니다.
이 때 'fibobacci(n-1)'은 'fibonacci(n)'의 이전 항을 계산하고, 'fibonacci(n-2)'는 그 이전 이전 항을 계산합니다.
따라서 이 과정이 반복되면서 피보나치 수열의 각 항이 계산됩니다.
아래는 'fibonacci(5)'를 호출했을 때의 코드 흐름입니다.
fibonacci(5)
= fibonacci(4) + fibonacci(3)
= (fibonacci(3) + fibonacci(2)) + (fibonacci(2) + fibonacci(1))
= ((fibonacci(2) + fibonacci(1)) + 2) + (1 + 1)
= ((1 + 1) + 2) + (1 + 1)
= 5따라서 'fibonacci(5)'의 결과는 5가 됩니다.
하노이의 탑
하노이의 탑 알고리즘은 원반을 다른 기둥으로 옮기는 문제로,
작은 원반부터 큰 원반 순서대로 쌓인 세 개의 기둥이 주어졌을 때,
모든 원반을 다른 기둥으로 옮기는 방법을 찾는 문제입니다.
아래는 C언어로 구현한 하노이의 탑 알고리즘 코드입니다.
#include <stdio.h>
void hanoi(int n, char from, char tmp, char to)
{
if (n == 1)
{
printf("%c -> %c\n", from, to);
}
else
{
hanoi(n - 1, from, to, tmp);
printf("%c -> %c\n", from, to);
hanoi(n - 1, tmp, from, to);
}
}
int main()
{
int n = 3; // 원반의 개수
hanoi(n, 'A', 'B', 'C');
return 0;
}
위 코드에서 'hanoi()' 함수는 원반의 개수 'n'과 출발점 'from', 임시저장소 'tmp', 도착점 'to'를 매개변수로 받아
하노이의 탑 알고리즘을 구현합니다. 'n'이 1 일때는 바로 출발점에서 도착점으로 원반을 옮기고, 그렇지 않을 때는
'hanoi()' 함수를 재귀적으로 호출하여 임시저장소를 이용해 원반을 옮기는 방식으로 구현됩니다.
하노이의 탑 알고리즘이 실생활에서는 타워크레인, 로봇 팔, 자동차의 변속기 등과 같은 곳에서 사용됩니다.
이러한 곳에서 하노이의 탑 알고리즘은 특정한 상황에서 객체들을 옮기는 문제를 해결할 때 사용됩니다.