Python 재귀함수 - 팩토리얼과 피보나치 수열

Python 재귀함수 - 팩토리얼과 피보나치 수열

재귀(recursive)

• 재귀 함수는 함수 내부에서 자기 자신을 호출하는 함수를 의미

팩토리얼

1! = 1   
2! = 1 * 2 ! = 1! * 2   
3! = 1 * 2 * 3 = 2! = 3   

fact(5)   
fact(fact(4) * 5 )   
fact(fact(fact(3) * 4 ) * 5 )

• 반복문

  # 팩토리얼 (다시 풀어보기)
  def fact(n):
    result = 1
    while n > 1:
        result *= n # result = result * n
        n -= 1  # n = n - 1
    return result
  fact(5)
  

• 재귀함수 ```python def factorial(n): if n <= 1: # n = 1일때의 의미 (0을 하게되면 계산한게 전체 0으 되기때문에 안됨) return 1 else: return factorial(n-1) * n # 10! = 9! * 10 = … = 1!

factorial(5)

### 피보나치 수열
``` python
F(n) = F(n-1) + F(n-2)
F(0) = F(1) = 1
F(2) = F(1) + F(0) = 1 + 1 = 2
F(3) = F(2) + F(1) = 2 + 1 = 3
F(4) = F(3) + F(2) = 3 + 2 = 5
F(5) = F(4) + F(3) = 5 + 3 = 8
F(6) = F(5) + F(4) = 8 + 5 = 13

• 반복 ```python def fib_loop(n): result = [1,1] for i in range(1,n): end1 = result[-1] end2 = result[len(result)-2] fib_num = end1 + end2

    result.append(fib_num)
  

  return result[-1]

fib_loop(100)

- 재귀
```python
#반복문과 다르게 오래걸림 (비효율적인 계산방식)
def fib_rec(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib_rec(n-1) + fib_rec(n-2)
fib_rec(100)