재귀란 무엇입니까?
함수가 자신을 직접 또는 간접적으로 호출하는 과정을 재귀라고 하고 해당 함수를 재귀 함수라고 합니다. 재귀 알고리즘을 사용하면 특정 문제를 매우 쉽게 해결할 수 있습니다. 그러한 문제의 예는 다음과 같습니다. 하노이 타워(TOH) , 중순/선주문/후순 트리 순회 , 그래프의 DFS 등. 재귀 함수는 자신의 복사본을 호출하고 원래 문제의 더 작은 하위 문제를 해결하여 특정 문제를 해결합니다. 필요할 때 더 많은 재귀 호출을 생성할 수 있습니다. 이 재귀 프로세스를 종료하려면 특정 사례를 제공해야 한다는 것을 아는 것이 중요합니다. 따라서 함수가 자신을 호출할 때마다 원래 문제의 더 간단한 버전을 사용한다고 말할 수 있습니다.
재귀의 필요성
재귀는 코드 길이를 줄이고 더 쉽게 읽고 쓸 수 있게 해주는 놀라운 기술입니다. 이는 나중에 논의할 반복 기술에 비해 몇 가지 장점이 있습니다. 유사한 하위 작업으로 정의할 수 있는 작업인 재귀는 이에 대한 최상의 솔루션 중 하나입니다. 예를 들어; 숫자의 계승.
재귀의 속성:
- 서로 다른 입력으로 동일한 작업을 여러 번 수행합니다.
- 모든 단계에서 우리는 문제를 더 작게 만들기 위해 더 작은 입력을 시도합니다.
- 재귀를 중지하려면 기본 조건이 필요합니다. 그렇지 않으면 무한 루프가 발생합니다.
알고리즘: 단계
The algorithmic steps for implementing recursion in a function are as follows: Step1 - Define a base case: Identify the simplest case for which the solution is known or trivial. This is the stopping condition for the recursion, as it prevents the function from infinitely calling itself. Step2 - Define a recursive case: Define the problem in terms of smaller subproblems. Break the problem down into smaller versions of itself, and call the function recursively to solve each subproblem. Step3 - Ensure the recursion terminates: Make sure that the recursive function eventually reaches the base case, and does not enter an infinite loop. step4 - Combine the solutions: Combine the solutions of the subproblems to solve the original problem.>
수학적 해석
프로그래머가 처음 n개의 자연수의 합을 결정해야 하는 문제를 고려해 보겠습니다. 이를 수행하는 방법에는 여러 가지가 있지만 가장 간단한 접근 방식은 단순히 1부터 n까지 숫자를 더하는 것입니다. 함수는 다음과 같습니다.
접근 방식(1) - 하나씩 추가하기만 하면 됩니다.
f(n) = 1 + 2 + 3 +…..+n
하지만 이것을 표현하는 또 다른 수학적 접근 방식이 있습니다.
접근법(2) – 재귀적 추가
f(n) = 1n=1
f(n) = n + f(n-1) n>1
접근 방식 (1)과 접근 방식 (2) 사이에는 간단한 차이점이 있으며 이는 다음과 같습니다. 접근법(2) 함수 에프( ) 그 자체가 함수 내부에서 호출되므로 이 현상을 재귀라고 하고, 재귀를 포함하는 함수를 재귀 함수라고 합니다. 결국 이것은 프로그래머가 일부 문제를 훨씬 쉽고 효율적으로 코딩할 수 있는 훌륭한 도구입니다. 방법.
재귀 함수는 메모리에 어떻게 저장되나요?
재귀 함수는 각 재귀 호출마다 스택에 추가하고 호출이 완료될 때까지 값을 유지하기 때문에 더 많은 메모리를 사용합니다. 재귀 함수는 스택 데이터 구조와 마찬가지로 LIFO(LAST IN FIRST OUT) 구조를 사용합니다. 스택 데이터 구조/
재귀의 기본 조건은 무엇입니까?
재귀 프로그램에서는 기본 사례에 대한 솔루션이 제공되고 더 큰 문제에 대한 솔루션은 더 작은 문제의 관점에서 표현됩니다.
int fact(int n) { if (n <= 1) // base case return 1; else return n*fact(n-1); }> 위의 예에서는 n <= 1에 대한 기본 사례가 정의되어 있으며 기본 사례에 도달할 때까지 더 작은 숫자로 변환하여 더 큰 숫자 값을 해결할 수 있습니다.
재귀를 사용하여 특정 문제를 어떻게 해결합니까?
아이디어는 하나 이상의 작은 문제로 문제를 표현하고 재귀를 중지하는 하나 이상의 기본 조건을 추가하는 것입니다. 예를 들어 (n-1)의 계승을 알고 있으면 계승 n을 계산합니다. 계승의 기본 사례는 n = 0입니다. n = 0이면 1을 반환합니다.
재귀에서 스택 오버플로 오류가 발생하는 이유는 무엇입니까?
기본 사례에 도달하지 않거나 정의되지 않은 경우 스택 오버플로 문제가 발생할 수 있습니다. 이것을 이해하기 위해 예를 들어보겠습니다.
int fact(int n) { // wrong base case (it may cause // stack overflow). if (n == 100) return 1; else return n*fact(n-1); }> 사실(10)이 호출되면 사실(9), 사실(8), 사실(7) 등을 호출하지만 숫자는 100에 도달하지 않습니다. 따라서 기본 사례에 도달하지 않습니다. 스택에서 이러한 함수로 인해 메모리가 소진되면 스택 오버플로 오류가 발생합니다.
직접 재귀와 간접 재귀의 차이점은 무엇입니까?
fun 함수가 동일한 함수 fun을 호출하는 경우 이를 직접 재귀라고 합니다. fun_new라는 다른 함수를 호출하고 fun_new가 fun을 직접 또는 간접적으로 호출하는 경우 fun 함수를 간접 재귀라고 합니다. 직접 재귀와 간접 재귀의 차이점은 표 1에 설명되어 있습니다.
// An example of direct recursion void directRecFun() { // Some code.... directRecFun(); // Some code... } // An example of indirect recursion void indirectRecFun1() { // Some code... indirectRecFun2(); // Some code... } void indirectRecFun2() { // Some code... indirectRecFun1(); // Some code... }> 꼬리 재귀와 꼬리가 없는 재귀의 차이점은 무엇입니까?
재귀 호출이 함수에 의해 마지막으로 실행되는 경우 재귀 함수는 꼬리 재귀입니다. 참조하시기 바랍니다 꼬리 재귀 기사 자세한 내용은.
재귀에서 다른 함수 호출에 메모리가 어떻게 할당됩니까?
main()에서 함수가 호출되면 메모리가 스택에 할당됩니다. 재귀 함수는 자신을 호출하고, 호출된 함수에 대한 메모리는 호출 함수에 할당된 메모리 위에 할당되며, 각 함수 호출에 대해 다른 지역 변수 복사본이 생성됩니다. 기본 사례에 도달하면 함수는 해당 값을 호출한 함수에 반환하고 메모리 할당이 취소되고 프로세스가 계속됩니다.
간단한 함수를 사용하여 재귀가 어떻게 작동하는지 예를 들어 보겠습니다.
CPP
// A C++ program to demonstrate working of> // recursion> #include> using> namespace> std;> > void> printFun(>int> test)> {> >if> (test <1)> >return>;> >else> {> >cout << test <<>' '>;> >printFun(test - 1);>// statement 2> >cout << test <<>' '>;> >return>;> >}> }> > // Driver Code> int> main()> {> >int> test = 3;> >printFun(test);> }> |
>
>
자바
애플릿
// A Java program to demonstrate working of> // recursion> class> GFG {> >static> void> printFun(>int> test)> >{> >if> (test <>1>)> >return>;> >else> {> >System.out.printf(>'%d '>, test);> >printFun(test ->1>);>// statement 2> >System.out.printf(>'%d '>, test);> >return>;> >}> >}> > >// Driver Code> >public> static> void> main(String[] args)> >{> >int> test =>3>;> >printFun(test);> >}> }> > // This code is contributed by> // Smitha Dinesh Semwal> |
>
>
파이썬3
# A Python 3 program to> # demonstrate working of> # recursion> > > def> printFun(test):> > >if> (test <>1>):> >return> >else>:> > >print>(test, end>=>' '>)> >printFun(test>->1>)># statement 2> >print>(test, end>=>' '>)> >return> > # Driver Code> test>=> 3> printFun(test)> > # This code is contributed by> # Smitha Dinesh Semwal> |
>
>
씨#
// A C# program to demonstrate> // working of recursion> using> System;> > class> GFG {> > >// function to demonstrate> >// working of recursion> >static> void> printFun(>int> test)> >{> >if> (test <1)> >return>;> >else> {> >Console.Write(test +>' '>);> > >// statement 2> >printFun(test - 1);> > >Console.Write(test +>' '>);> >return>;> >}> >}> > >// Driver Code> >public> static> void> Main(String[] args)> >{> >int> test = 3;> >printFun(test);> >}> }> > // This code is contributed by Anshul Aggarwal.> |
>
>
PHP
// PHP program to demonstrate // working of recursion // function to demonstrate // working of recursion function printFun($test) { if ($test <1) return; else { echo('$test '); // statement 2 printFun($test-1); echo('$test '); return; } } // Driver Code $test = 3; printFun($test); // This code is contributed by // Smitha Dinesh Semwal. ?>> |
>
>
자바스크립트
> > // JavaScript program to demonstrate working of> // recursion> > function> printFun(test)> >{> >if> (test <1)> >return>;> >else> {> >document.write(test +>' '>);> >printFun(test - 1);>// statement 2> >document.write(test +>' '>);> >return>;> >}> >}> > // Driver code> >let test = 3;> >printFun(test);> > > |
>
>산출
3 2 1 1 2 3>
시간 복잡도: 오(1)
보조 공간: 오(1)
언제 인쇄재미(3) main()에서 호출되고 메모리가 할당됩니다. 인쇄재미(3) 아래 다이어그램과 같이 지역 변수 test가 3으로 초기화되고 명령문 1~4가 스택에 푸시됩니다. 먼저 '3'을 인쇄합니다. 진술 2에서, 인쇄재미(2) 호출되고 메모리가 할당됩니다. 인쇄재미(2) 지역 변수 test는 2로 초기화되고 명령문 1부터 4까지가 스택에 푸시됩니다. 비슷하게, 인쇄재미(2) 전화 인쇄재미(1) 그리고 인쇄재미(1) 전화 프린트펀(0) . 프린트펀(0) if 문으로 가서 다음으로 돌아갑니다. 인쇄재미(1) . 나머지 진술은 인쇄재미(1) 실행되어 다음으로 돌아갑니다. 인쇄재미(2) 등등. 출력에는 3부터 1까지의 값이 인쇄된 다음 1부터 3까지의 값이 인쇄됩니다. 메모리 스택은 아래 다이어그램에 표시되어 있습니다.
재귀 VS 반복
| SR 번호 | 재귀 | 반복 |
| 1) | 기본 사례가 참이 되면 종료됩니다. | 조건이 거짓이 되면 종료됩니다. |
| 2) | 기능과 함께 사용됩니다. | 루프와 함께 사용됩니다. |
| 삼) | 모든 재귀 호출에는 스택 메모리에 추가 공간이 필요합니다. | 모든 반복에는 추가 공간이 필요하지 않습니다. |
| 4) | 코드 크기가 더 작습니다. | 더 큰 코드 크기. |
이제 재귀를 사용하여 해결할 수 있는 몇 가지 실제 문제에 대해 논의하고 기본 작동을 이해해 보겠습니다. 기본적인 이해를 위해 다음 글을 읽어보시기 바랍니다.
재귀에 대한 기본 이해.
문제 1: n>2 일 때 n의 피보나치 수열을 구하는 프로그램과 반복 관계를 작성하세요.
수학 방정식:
n if n == 0, n == 1; fib(n) = fib(n-1) + fib(n-2) otherwise;>
재발 관계:
T(n) = T(n-1) + T(n-2) + O(1)>
재귀 프로그램:
Input: n = 5 Output: Fibonacci series of 5 numbers is : 0 1 1 2 3>
구현:
C++
// C++ code to implement Fibonacci series> #include> using> namespace> std;> > // Function for fibonacci> > int> fib(>int> n)> > > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >cout<<>'Fibonacci series of 5 numbers is: '>;> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { cout<' '; } return 0; }> |
>
>
씨
// C code to implement Fibonacci series> #include> > // Function for fibonacci> int> fib(>int> n)> > >// Stop condition> >if> (n == 0)> >return> 0;> > >// Stop condition> >if> (n == 1> > // Driver Code> int> main()> {> >// Initialize variable n.> >int> n = 5;> >printf>(>'Fibonacci series '> >'of %d numbers is: '>,> >n);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i printf('%d ', fib(i)); } return 0; }> |
>
>
자바
포티네니 램
// Java code to implement Fibonacci series> import> java.util.*;> > class> GFG> {> > // Function for fibonacci> static> int> fib(>int> n)> > > // Driver Code> public> static> void> main(String []args)> {> > >// Initialize variable n.> >int> n =>5>;> >System.out.print(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i =>0>; i { System.out.print(fib(i)+' '); } } } // This code is contributed by rutvik_56.> |
>
>
파이썬3
# Python code to implement Fibonacci series> > # Function for fibonacci> def> fib(n):> > ># Stop condition> >if> (n>=>=> 0>):> >return> 0> > ># Stop condition> >if> (n>=>=> 1> or> n>=>=> 2>):> >return> 1> > ># Recursion function> >else>:> >return> (fib(n>-> 1>)>+> fib(n>-> 2>))> > > # Driver Code> > # Initialize variable n.> n>=> 5>;> print>(>'Fibonacci series of 5 numbers is :'>,end>=>' '>)> > # for loop to print the fibonacci series.> for> i>in> range>(>0>,n):> >print>(fib(i),end>=>' '>)> |
>
>
씨#
using> System;> > public> class> GFG> {> > >// Function for fibonacci> >static> int> fib(>int> n)> > n == 2)> >return> 1;> > >// Recursion function> >else> >return> (fib(n - 1) + fib(n - 2));> >> > >// Driver Code> >static> public> void> Main ()> >{> > >// Initialize variable n.> >int> n = 5;> >Console.Write(>'Fibonacci series of 5 numbers is: '>);> > >// for loop to print the fibonacci series.> >for> (>int> i = 0; i { Console.Write(fib(i) + ' '); } } } // This code is contributed by avanitrachhadiya2155> |
>
>
자바스크립트
> // JavaScript code to implement Fibonacci series> > // Function for fibonacci> function> fib(n)> n == 2)> >return> 1;> >// Recursion function> >else> >return> fib(n-1) + fib(n-2);> > > // Initialize variable n.> let n = 5;> > document.write(>'Fibonacci series of 5 numbers is: '>);> > // for loop to print the fibonacci series.> for>(let i = 0; i { document.write(fib(i) + ' '); }> |
>
>산출
Fibonacci series of 5 numbers is: 0 1 1 2 3>
시간 복잡도: 오(2N)
보조 공간: 에)
서명되지 않은 int c 프로그래밍
다음은 큰 문제가 어떻게 작은 문제로 해결될 수 있는지에 대한 명확한 그림을 보여주는 입력 5에 대한 재귀 트리입니다.
fib(n)은 피보나치 함수입니다. 주어진 프로그램의 시간 복잡도는 함수 호출에 따라 달라질 수 있습니다.
fib(n) -> 레벨 CBT(UB) -> 2^n-1 노드 -> 2^n 함수 호출 -> 2^n*O(1) -> T(n) = O(2^n)
최선의 경우.
T(n) = ?(2^n2)>
일하고 있는:
문제 2: n>2 일 때 n의 팩토리얼을 구하는 프로그램과 반복 관계를 작성하세요.
수학 방정식:
1 if n == 0 or n == 1; f(n) = n*f(n-1) if n>1;>
재발 관계:
T(n) = 1 for n = 0 T(n) = 1 + T(n-1) for n>0>
재귀 프로그램:
입력: n = 5
산출:
5의 계승은 120입니다.
구현:
C++
// C++ code to implement factorial> #include> using> namespace> std;> > // Factorial function> int> f(>int> n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> > > // Driver code> int> main()> {> >int> n = 5;> >cout<<>'factorial of '><' is: '< return 0; }> |
>
>
씨
// C code to implement factorial> #include> > // Factorial function> int> f(>int> n)> > >// Stop condition> >if> (n == 0> > // Driver code> int> main()> {> >int> n = 5;> >printf>(>'factorial of %d is: %d'>, n, f(n));> >return> 0;> }> |
>
>
자바
// Java code to implement factorial> public> class> GFG> {> > >// Factorial function> >static> int> f(>int> n)> >> > >// Driver code> >public> static> void> main(String[] args)> >{> >int> n =>5>;> >System.out.println(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyesh072019.> |
>
>
파이썬3
# Python3 code to implement factorial> > # Factorial function> def> f(n):> > ># Stop condition> >if> (n>=>=> 0> or> n>=>=> 1>):> >return> 1>;> > ># Recursive condition> >else>:> >return> n>*> f(n>-> 1>);> > > # Driver code> if> __name__>=>=>'__main__'>:> > >n>=> 5>;> >print>(>'factorial of'>,n,>'is:'>,f(n))> > ># This code is contributed by pratham76.> |
>
>
씨#
// C# code to implement factorial> using> System;> class> GFG {> > >// Factorial function> >static> int> f(>int> n)> > n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n * f(n - 1);> >> > >// Driver code> >static> void> Main()> >{> >int> n = 5;> >Console.WriteLine(>'factorial of '> + n +>' is: '> + f(n));> >}> }> > // This code is contributed by divyeshrabadiya07.> |
>
>
자바스크립트
> // JavaScript code to implement factorial> > // Factorial function> function> f(n)> n == 1)> >return> 1;> > >// Recursive condition> >else> >return> n*f(n-1);> > > // Initialize variable n.> let n = 5;> document.write(>'factorial of '>+ n +>' is: '> + f(n));> > // This code is contributed by probinsah.> > |
>
>산출
factorial of 5 is: 120>
시간 복잡도: 에)
보조 공간: 에)
일하고 있는:
사용자 입력에 대한 계승 재귀 함수 다이어그램 5.
예: 실제 문제에 대한 재귀의 실제 적용
재귀는 컴퓨터 과학 및 프로그래밍 분야에 많이 응용되는 강력한 기술입니다. 재귀의 일반적인 응용 프로그램은 다음과 같습니다.
- 트리 및 그래프 순회 : 재귀는 트리 및 그래프와 같은 데이터 구조를 순회하고 검색하는 데 자주 사용됩니다. 재귀 알고리즘을 사용하면 트리나 그래프의 모든 노드나 정점을 체계적인 방식으로 탐색할 수 있습니다. 정렬 알고리즘 : 재귀 알고리즘은 퀵 정렬, 병합 정렬 등의 정렬 알고리즘에도 사용됩니다. 이러한 알고리즘은 재귀를 사용하여 데이터를 더 작은 하위 배열 또는 하위 목록으로 나누고 정렬한 다음 다시 병합합니다. 분할 정복 알고리즘: 이진 검색 알고리즘과 같이 분할 정복 접근 방식을 사용하는 많은 알고리즘은 재귀를 사용하여 문제를 더 작은 하위 문제로 분해합니다. 프랙탈 생성: 재귀 알고리즘을 사용하여 프랙탈 모양과 패턴을 생성할 수 있습니다. 예를 들어, 만델브로 집합은 복소수에 재귀 공식을 반복적으로 적용하여 생성됩니다. 역추적 알고리즘: 역추적 알고리즘은 각 결정이 이전 결정에 따라 달라지는 일련의 결정을 내리는 문제를 해결하는 데 사용됩니다. 이러한 알고리즘은 재귀를 사용하여 구현되어 가능한 모든 경로를 탐색하고 솔루션을 찾을 수 없을 때 역추적할 수 있습니다. Memoization : Memoization은 비용이 많이 드는 함수 호출의 결과를 저장하고 동일한 입력이 다시 발생할 때 캐시된 결과를 반환하는 기술입니다. 하위 문제의 결과를 계산하고 캐시하는 재귀 함수를 사용하여 메모를 구현할 수 있습니다.
이는 컴퓨터 과학 및 프로그래밍 분야에서 재귀를 적용하는 몇 가지 예일 뿐입니다. 재귀는 다양한 유형의 문제를 해결하는 데 사용할 수 있는 다재다능하고 강력한 도구입니다.
설명: 재귀의 실제 예 중 하나:
재귀는 자신을 호출하는 함수와 관련된 프로그래밍 기술입니다. 복잡한 문제를 해결하기 위한 강력한 도구일 수 있지만 무한 루프 및 스택 오버플로를 방지하려면 신중한 구현이 필요합니다.
다음은 Python에서 재귀를 구현하는 예입니다.
C++
#include> using> namespace> std;> int> factorial(>int> n)> {> > >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > int> main()> {> > >// Call the factorial function and print the result> >int> result = factorial(5);> >cout << result |
>
>
자바
import> java.util.*;> > class> Main {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n ==>0> || n ==>1>) {> >return> 1>;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n ->1>);> >}> >}> > >public> static> void> main(String[] args)> >{> >// Call the factorial function and print the result> >int> result = factorial(>5>);> >System.out.println(result);>// Output: 120> >}> }> |
>
>
파이썬3
def> factorial(n):> ># Base case: if n is 0 or 1, return 1> >if> n>=>=> 0> or> n>=>=> 1>:> >return> 1> > ># Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else>:> >return> n>*> factorial(n>->1>)> > # Call the factorial function and print the result> result>=> factorial(>5>)> print>(result)># Output: 120> |
>
>
씨#
저녁과 저녁의 차이
using> System;> > class> MainClass {> >public> static> int> factorial(>int> n)> >{> >// Base case: if n is 0 or 1, return 1> >if> (n == 0 || n == 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1,> >// call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> >}> > >public> static> void> Main (>string>[] args) {> >// Call the factorial function and print the result> >int> result = factorial(5);> >Console.WriteLine(result);>// Output: 120> >}> }> |
>
>
자바스크립트
function> factorial(n) {> >// Base case: if n is 0 or 1, return 1> >if> (n === 0 || n === 1) {> >return> 1;> >}> > >// Recursive case: if n is greater than 1, call the function with n-1 and multiply by n> >else> {> >return> n * factorial(n - 1);> >}> }> > // Call the factorial function and print the result> const result = factorial(5);> console.log(result);>// Output: 120> |
>
>산출
120>
이 예에서는 정수 n을 입력으로 사용하는 계승이라는 함수를 정의합니다. 이 함수는 재귀를 사용하여 n의 계승(즉, n까지의 모든 양의 정수의 곱)을 계산합니다.
계승 함수는 먼저 n이 기본 사례인 0 또는 1인지 확인합니다. n이 0 또는 1이면 0!이므로 함수는 1을 반환합니다. 그리고 1! 둘 다 1이다.
n이 1보다 크면 함수는 재귀 사례로 들어갑니다. n-1을 인수로 사용하여 자신을 호출하고 결과에 n을 곱합니다. 이것은 n을 계산합니다! (n-1)을 재귀적으로 계산하여!.
재귀는 주의 깊게 사용하지 않으면 비효율적일 수 있으며 스택 오버플로로 이어질 수 있다는 점에 유의하는 것이 중요합니다. 각 함수 호출은 호출 스택에 새 프레임을 추가하므로 재귀가 너무 깊어지면 스택이 너무 커질 수 있습니다. 또한 재귀를 사용하면 여러 수준의 함수 호출을 고려해야 하므로 코드를 이해하고 디버그하기가 더 어려워질 수 있습니다.
그러나 재귀는 복잡한 문제, 특히 문제를 더 작은 하위 문제로 나누는 문제를 해결하기 위한 강력한 도구가 될 수도 있습니다. 올바르게 사용하면 재귀를 사용하면 코드를 더욱 우아하고 읽기 쉽게 만들 수 있습니다.
반복 프로그래밍에 비해 재귀 프로그래밍의 단점은 무엇입니까?
재귀 프로그램과 반복 프로그램은 모두 동일한 문제 해결 능력을 가지고 있습니다. 즉, 모든 재귀 프로그램은 반복적으로 작성될 수 있으며 그 반대의 경우도 마찬가지입니다. 재귀 프로그램은 기본 사례에 도달할 때까지 모든 기능이 스택에 유지되므로 반복 프로그램보다 더 많은 공간 요구 사항을 갖습니다. 또한 함수 호출 및 반환 오버헤드로 인해 더 많은 시간이 필요합니다.
게다가 코드의 길이가 짧기 때문에 코드를 이해하기 어렵기 때문에 코드를 작성할 때 각별한 주의가 필요합니다. 재귀 호출을 제대로 검사하지 않으면 컴퓨터의 메모리가 부족해질 수 있습니다.
반복 프로그래밍에 비해 재귀 프로그래밍의 장점은 무엇입니까?
재귀는 코드를 작성하는 깔끔하고 간단한 방법을 제공합니다. 일부 문제는 트리 순회와 같이 본질적으로 재귀적입니다. 하노이 타워 등. 이러한 문제의 경우 재귀적인 코드를 작성하는 것이 좋습니다. 스택 데이터 구조를 사용하여 이러한 코드를 반복적으로 작성할 수도 있습니다. 예를 들어 재귀 없는 중위 트리 순회, 하노이 반복 타워를 참조하세요.
재귀 요약:
- 재귀에는 두 가지 유형의 사례, 즉 재귀 사례와 기본 사례가 있습니다.
- 기본 사례는 해당 사례가 참으로 판명될 때 재귀 함수를 종료하는 데 사용됩니다.
- 각 재귀 호출은 스택 메모리에 해당 메서드의 새 복사본을 만듭니다.
- 무한 재귀로 인해 스택 메모리가 부족해질 수 있습니다.
- 재귀 알고리즘의 예: 병합 정렬, 빠른 정렬, 하노이 타워, 피보나치 시리즈, 요인 문제 등
초보자를 위한 출력 기반 연습 문제:
재귀 연습 문제 | 세트 1
재귀 연습 문제 | 세트 2
재귀 연습 문제 | 세트 3
재귀 연습 문제 | 세트 4
재귀 연습 문제 | 세트 5
재귀 연습 문제 | 세트 6
재귀 연습 문제 | 세트 7
재귀에 관한 퀴즈
재귀 코딩 연습:
재귀에 관한 모든 기사
솔루션이 포함된 재귀 연습 문제