재귀 함수는 자신을 직접 또는 간접적으로 호출하는 루틴으로 정의할 수 있습니다.
즉, 재귀 함수는 동일한 문제의 더 작은 인스턴스를 해결하여 문제를 해결하는 함수입니다. 이 기술은 더 간단하고 유사한 하위 문제로 나눌 수 있는 문제를 해결하기 위해 프로그래밍에서 일반적으로 사용됩니다.
재귀 함수의 필요성:
재귀 함수는 동일한 문제의 더 작은 인스턴스를 해결하여 문제를 해결하는 함수입니다. 이 기술은 더 간단하고 유사한 하위 문제로 나눌 수 있는 문제를 해결하기 위해 프로그래밍에서 자주 사용됩니다.
자바 이진 트리
1. 복잡한 작업 해결:
재귀 함수는 복잡한 문제를 동일한 문제의 더 작은 인스턴스로 나누어 컴팩트하고 읽기 쉬운 코드를 만듭니다.
2. 분열과 정복:
재귀 함수는 병합 정렬 및 퀵 정렬과 같은 분할 정복 알고리즘, 문제를 더 작은 하위 문제로 나누고 재귀적으로 해결하고 솔루션을 원래 문제와 병합하는 데 적합합니다.
삼. 역추적 :
재귀 역추적은 N-Queens 및 Sudoku와 같은 문제를 탐색하고 해결하는 데 이상적입니다.
4. 동적 프로그램 작성:
재귀 함수는 하위 문제를 해결하고 해당 솔루션을 완전한 솔루션으로 결합하여 동적 프로그래밍 문제를 효율적으로 해결합니다.
5. 나무와 그래프 구조:
재귀 함수는 트리 및 그래프 구조 작업에 적합하며 순회 및 패턴 인식 작업을 단순화합니다. .
재귀 함수를 작성하는 방법:
재귀 함수의 구성요소:
기본 케이스: 모든 재귀 함수에는 기본 사례가 있어야 합니다. 기본 사례는 추가 재귀가 필요하지 않은 가장 간단한 시나리오입니다. 이는 함수가 자신을 무한정 호출하는 것을 방지하는 종료 조건입니다. 적절한 기본 사례가 없으면 재귀 함수는 무한 재귀로 이어질 수 있습니다.
재귀적 사례: 재귀적인 경우 함수는 수정된 인수를 사용하여 자신을 호출합니다. 이것이 재귀의 본질입니다. 더 큰 문제를 동일한 문제의 더 작은 인스턴스로 나누어 해결하는 것입니다. 재귀 사례는 각 반복마다 기본 사례에 더 가깝게 이동해야 합니다.
의 예를 고려해 봅시다 숫자의 계승 :
이 예에서 기본 사례는 다음과 같습니다. N ~이다 0 , 함수는 다음을 반환합니다. 1 . 재귀 사례가 곱해집니다. N 매개변수로 호출된 함수의 결과 엔 - 1 . 기본 사례에 도달할 때까지 프로세스가 계속됩니다.
재귀 함수에 올바른 기본 사례가 있고 재귀 호출이 기본 사례로 이어지는지 확인하는 것이 중요합니다. 그렇지 않으면 프로시저가 무기한 실행되어 스택 오버플로(함수 호출에 할당된 사용 가능한 메모리 초과)로 이어질 수 있습니다.
다음은 숫자의 계승을 구현한 것입니다.
C++ #include using namespace std; // Recursive Function to calculate Factorial of a number int factorial(int n) { // Base case if (n == 0) { return 1; } // Recursive case return n * factorial(n - 1); } // Driver Code int main() { int n = 4; cout << 'Factorial of ' << n << ' is:' << factorial(n); return 0; }> 자바 import java.util.Scanner; public class Factorial { // Recursive Function to calculate the factorial of a number static int factorial(int n) { // Base case: If n is 0, the factorial is 1. if (n == 0) { return 1; } // Recursive case: Calculate the factorial by multiplying n with the factorial of (n - 1). return n * factorial(n - 1); } public static void main(String[] args) { int n = 4; // Calculate and print the factorial of n. int result = factorial(n); System.out.println('Factorial of ' + n + ' is: ' + result); } }> 파이썬 # Recursive Function to calculate Factorial of a number def factorial(n): # Base case if n == 0: return 1 # Recursive case return n * factorial(n - 1) # Driver Code if __name__ == '__main__': n = 4 print('Factorial of', n, 'is:', factorial(n))> 씨# using System; class Program { // Recursive Function to calculate Factorial of a number static int Factorial(int n) { // Base case if (n == 0) { return 1; } // Recursive case return n * Factorial(n - 1); } // Driver Code static void Main() { int n = 4; Console.WriteLine('Factorial of ' + n + ' is: ' + Factorial(n)); } }> 자바스크립트 // Function to calculate the factorial of a number using recursion function factorial(n) { // Base case: If n is 0, the factorial is 1. if (n === 0) { return 1; } // Recursive case: Calculate the factorial by multiplying n with the factorial of (n - 1). return n * factorial(n - 1); } // Main function function main() { // Given number let n = 4; // Calculate the factorial of n. let result = factorial(n); // Print the result console.log('Factorial of ' + n + ' is: ' + result); } // Call the main function main();> 산출
Factorial of 4 is:24>
시간 복잡도: 에)
보조 공간: 에)