C 언어에서의 재귀

안녕하세요, 미래의 프로그래머 여러분! 오늘 우리는 프로그래밍에서 가장 매력적인 개념 중 하나에 대해 깊이 알아보게 될 것입니다: 재귀. 재귀라는 단어가 무서울 것 같지 마세요 - 이 튜토리얼이 끝나면 여러분은 재귀의 달인이 될 것입니다! 이 흥미로운 여정을 함께 떠나보겠습니다.

C - Recursion

C 언어에서 재귀 함수는 무엇인가요?

자신을 거울 속에서 보고, 뒤에 또 다른 거울이 있는 상상을 해보세요. 무한한 수의 자신의 반영을 볼 수 있습니다. 이것은 프로그래밍에서의 재귀와 비슷합니다!

재귀 함수는 자신을 호출하는 함수입니다. 마치 함수가 "Hey, 나는 도움이 필요해. 나를 도와줄 사람은 누구일까?... 나 самого!"라고 말하는 것과 같습니다.

다음은 간단한 예제입니다:

void countdown(int n) {
if (n == 0) {
printf("Blastoff!\n");
} else {
printf("%d\n", n);
countdown(n - 1);
}
}

이 함수에서 countdown은 매번 더 작은 숫자로 자신을 호출합니다. 이는 로켓 카운트다운과 같아서, 0에 도달하기 전까지 계속 카운트하고 그런 다음 blastoff!

C 언어에서 재귀가 왜 사용될까요?

"루프가 있잖아 왜 재귀를 귀찮게 하지?"라고 궁금할 수 있습니다. 훌륭한 질문입니다! 재귀는 다음과 같은 여러 가지 장점이 있습니다:

특정 문제에 대해 코드를 더 읽기 쉽고 우아하게 만들 수 있습니다.
트리와 같은 구조를 탐색하는 데 최적입니다.
복잡한 루프 구조와 임시 변수의 필요성을 줄일 수 있습니다.

그러나 재귀는 항상 최고의 선택이 아닙니다. 메모리 소모가 많고 일부 문제에 대해 더 느릴 수 있습니다. 프로그래밍에서 많은 것들처럼, 적절한 도구를 선택하는 것입니다.

재귀를 사용한 팩토리얼 계산

재귀의 고전적인 예제 중 하나를 보겠습니다: 팩토리얼 계산. 숫자 n의 팩토리얼 (n!라고 쓰입니다)은 n 이하의 모든 양수의 곱입니다.

다음은 팩토리얼을 재귀로 계산하는 방법입니다:

int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

이를 설명해보겠습니다:

n이 0이나 1이라면 1을 반환합니다 (이는 우리의 기본 사례입니다).
그렇지 않으면 n을 (n-1)의 팩토리얼로 곱합니다.

그래서 factorial(5)를 호출하면 다음이 일어납니다:

5 * factorial(4)
5 (4 factorial(3))
5 (4 (3 * factorial(2)))
5 (4 (3 (2 factorial(1))))
5 (4 (3 (2 1)))
5 (4 (3 * 2))
5 (4 6)
5 * 24
120

그래서 5! = 120입니다.

재귀를 사용한 이진 검색

이진 검색은 정렬된 목록에서 요소를 찾는 효율적인 알고리즘입니다. 이는 반복적으로 검색 구간을 반으로 나눕니다. 재귀적으로 구현해 보겠습니다:

int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;

if (arr[mid] == x)
return mid;

if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

return binarySearch(arr, mid + 1, r, x);
}

return -1;
}

이 함수는 다음을 수행합니다:

중간 인덱스를 계산합니다.
중간 요소가 목표라면 끝!
목표가 중간 요소보다 작다면 왼쪽 반을 검색합니다.
목표가 중간 요소보다 크다면 오른쪽 반을 검색합니다.
요소를 찾을 수 없다면 -1을 반환합니다.

이는 고급 기술版的 "숫자 맞추기"와 같아요!

재귀를 사용한 피보나치 수열 생성

피보나치 수열은 각 요소가 전的两个 요소의 합인 수열입니다. 이는 재귀에 최적입니다!

다음은 피보나치 수를 재귀적으로 생성하는 방법입니다:

int fibonacci(int n) {
if (n <= 1)
return n;
return fibonacci(n-1) + fibonacci(n-2);
}

이 함수는 다음과 같이 작동합니다:

n이 0이나 1이라면 n을 반환합니다 (이는 우리의 기본 사례입니다).
그렇지 않으면 전两个 피보나치 수를 더합니다.

그래서 fibonacci(5)를 호출하면 다음이 일어납니다:

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)
fibonacci(2) = fibonacci(1) + fibonacci(0)
fibonacci(1) = 1
fibonacci(0) = 0

역으로 계산하면:

fibonacci(2) = 1 + 0 = 1
fibonacci(3) = 1 + 1 = 2
fibonacci(4) = 2 + 1 = 3
fibonacci(5) = 3 + 2 = 5

그래서 5번째 피보나치 수는 5입니다!

일반 재귀 메서드

다음은 우리가 논의한 일반 재귀 메서드 표입니다:

메서드	설명	기본 사례	재귀 사례
팩토리얼	n! 계산	n = 0 또는 1	n * factorial(n-1)
이진 검색	정렬된 배열에서 요소 찾기	요소 찾음 또는 배열에 없음	왼쪽 또는 오른쪽 반 검색
피보나치	피보나치 수 생성	n <= 1	fibonacci(n-1) + fibonacci(n-2)

재귀를 이해하는 열쇠는 재귀 호출이 올바르게 작동할 것이라고 믿는 것입니다. 자신을 위임하는 것처럼, 자신과 같은 복제본이 任务을 처리할 것이라고 믿습니다!

재귀는처음에는 약간 혼란스러울 수 있지만, 연습하면 프로그래밍 도구箱에서 강력한 도구가 됩니다. 계속 실험하고, 재귀적 해결책을 어디서든 볼 수 있게 될 것입니다!

행복하게 코딩하세요, 그리고 기억하세요 - 재귀를 이해하려면 먼저 재귀를 이해해야 합니다. ?

Credits: Image by storyset