[DataScience Computing] Recursive Algorithms(재귀 함수)

1️⃣ Recursive Algorithm(재귀 함수)

재귀함수란 알고리즘이나 함수가 문제를 해결하기 위해 자기 자신을 다시 호출하는 기능이다. 정의 자체가 재귀적일 때 적합하다.

 

 

 

2️⃣ 재귀 함수의 종류

✔ 1. Calculate Factorial(팩토리얼 계산)

팩토리얼은 자기 자신을 다시 곱해야 하기에 재귀함수에 적절하다.

✔ 2. Fibonacci Sequence(피보나치 수열)

 

✔ 그 외 : Binomial Coefficient, Tower of Hanoi, Binary Search …

 

 

3️⃣ Factorial Calculation

• Time Complextiy(시간 복잡도)
  • 우선 팩토리얼 계산의 시간 복잡도는 O(n)이다. 이는 함수가 자기 자신을 정확히 n번 호출하기 때문이다. 팩토리얼 함수 factorial(n)은 n이 0이나 1일 경우에 바로 결과를 반환하고, 그렇지 않은 경우 n * factorial(n-1)을 계산하게 된다. 따라서, n이 2 이상일 때마다 함수는 자신을 한 번 더 호출하고, 이는 n에 대해 선형적으로 증가한다. 각 호출에서는 상수 시간 작업이 수행되므로 전체 시간 복잡도는 O(n)이 된다.
     
     
• Python 코드 예제

 

• 이 코드는 factorial 함수를 정의하고, 이 함수는 하나의 매개변수 n을 받는다.
• 함수는 n이 0일 때 1을 반환하며, 그 외의 경우에는 n과 factorial(n-1)의 곱을 반환한다.
• 이 예제에서는 factorial(5)를 호출하여 5의 팩토리얼을 계산하고, 그 결과를 출력한다.