[python] 재귀함수(Recursive Function) / TIL_220919

재귀함수란 함수 안에서 함수 자기자신을 호출하여 작업을 수행하는 방식의 함수이다.

 

재귀함수를 활용하여 팩토리얼 구현해보기!

팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 값

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

n = int(input())
print(factorial(n))

 

factorial(n) 함수 내에 결과값으로 factorial(n-1)을 가지고 오면서 탈출 조건에 만족할 때까지 반복 수행하게 된다.

탈출 조건은 n == 0 일 때, 1을 return 하기 때문에 아래와 같은 결과값을 얻을 수 있음

 

n이 1 일 때, return n * factorial(n-1)  -> 1 * 1 = 1

n이 2 일 때, return n * factorial(n-1) -> 2 * 1  = 2

n이 3 일 때, return n * factorial(n-1) -> 3 * 2 = 6

n이 4 일 때, return n * factorial(n-1) -> 4 * 6 = 24

...

 

피보나치 수열 구하는 방법도 재귀함수를 활용하여 구현할 수 있다.

피보나치 수열는 앞의 두 수의 합이 바로 뒤의 수가 되는 수의 배열을 말한다.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, .....

def fibo(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return fibo(n - 2) + fibo(n - 1)

n = int(input())
print(fibo(n))

 

 

마찬가지로 탈출 조건이 주어졌기 때문에 재귀함수를 통해 아래와 같이 반복 수행을 하게 된다.

n이 3일 때, return fibo(n - 2) + fibo(n - 1) - > 1 + 1 = 2

n이 4일 때, return fibo(n - 2) + fibo(n - 1) - > 1 + 2 = 3

n이 5일 때, return fibo(n - 2) + fibo(n - 1) - > 2 + 3 = 5

n이 6일 때, return fibo(n - 2) + fibo(n - 1) - > 3 + 5 = 8

...