(Python) 재귀함수(Recursive function)란?

 

평소에 재귀함수 구현에 관심이 있었지만, 바쁘다는 핑계로 미루다보니 벌써 5월 중순쯤에 포스팅을 하게 되었다.

https://dojang.io/mod/page/view.php?id=2352 

파이썬 코딩 도장: 31.1 재귀호출 사용하기

 

함수 안에서 함수 자기자신을 호출하는 방식을 Recursive call이라고 한다.
반복문 코드보다 재귀호출로 구현한 코드가 좀 더 직관적이고 이해하기 쉬운 경우가 많다.

def hello():
    print('Hello, world!')
    hello()

hello()

----------------------결과값----------------------
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
.
.
.
Hello, world!
RecursionError: maximum recursion depth exceeded while calling a Python object

간단한 파이썬 예시이다.

 

함수안에 print('Hello, world')가 호출되고, 3번째 줄 hello()로 인해 재호출 되는 상황이다.

하지만, 나중에 RecursionError가 뜨는데, 이는 파이썬 최대 재귀 깊이가 1,000으로 설정되어 있어 그렇다.

 

※ 재귀호출을 사용하려면 반드시 종료 조건을 만들어주어야 한다.

def hello(count):
    if count == 0:
        return
    print('hello world!', count)
    count = count - 1
    hello(count)

hello(5)

----------------------결과값----------------------
hello world! 5
hello world! 4
hello world! 3
hello world! 2
hello world! 1

 

※ 재귀 호출로 팩토리얼 구해보기

factorial이란 그 수보다 작거나 같은 모든 야의 정수의 곱이다. n이 하나의 자연수일 때, 1에서 n까지의 모든 자연수의 곱을 n에 상대하여 이르는 말이다. 기호는 '!' 를 쓰며 '팩토리얼'이라고 읽는다.

출처: https://ko.wikipedia.org/wiki/%EA%B3%84%EC%8A%B9

예를들면 5의 팩토리얼을 구하고싶으면 1부터 5까지의 수를 모두 곱하면 된다.

→ 1x2x3x4x5 = 120(5의 팩토리얼)

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

print(factorial(5))


----------------------결과값----------------------
120

n==1 이면 해당 값을 그대로 return 해주면 되고, 1이 아니면 '해당 수 * 해당 수 -1' 값을 재귀함수로 호출시켜주면 된다

 

그러면 이제부터 재귀함수를 이용해서 피보나치 수열을 구해보자.

 

※ 피보나치 수열 구하기

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
처음 여섯 항은 각각 0, 1, 1, 2, 3, 5, 8 이다 편의상 0번째 항을 0으로 두기도 한다.

출처: https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

 

먼저 첫번째와 두번째 인덱스 값은 1이므로 n의 값이 1 or 2가 들어오면 1를 return 해준다.

def Fibonacci(n):
    if n == 1 or n == 2:
        return 1

print(Fibonacci(2))

 

0번째 항을 찾을 수 도 있으니 0번쨰 항을 물어보면 0을 return 해준다.

    if n == 0:
        return 0

그리고 피보나치를 재귀함수로 푸는사람이 많지만, 나는 list를 생성해서 한 번 풀어보겠다.(생각해보니 주제는 재귀함순인데..)

 

입력받은 수 만큼 피보나치 수열을 실행해야 하기 때문에 for문이 필요하다.

for i in range(3, n+1):

 

이 부분은 피보나치 수열을 구현하기 위한 부분인데, 피보나치 수열을 잘 보면

'내가 원하는 항' =  '내가 원하는 항 - 1' + '내가 원하는 항 - 2' 를 더해야 한다. 

lst.append(lst[i-1]+lst[i-2])

 

그리고 나서 아래부분에 내가 알고싶은 항의 숫자를 넣으면 알맞게 나오는 것이다.

value = int(input())  # 수열의 알고 싶은 항
Fibonacci(value)

 

※전체코드

def Fibonacci(n):
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    lst = [0, 1, 1]
    for i in range(3, n+1):
        lst.append(lst[i-1]+lst[i-2])
    print(lst[-1])


value = int(input())  # 수열의 알고 싶은 항
Fibonacci(value)

5번째 항의 값은 5이다.

 

6번째 항의 값은 8인것을 알 수 있다.

 

-------------------재귀함수로 피보나치를 푸는 방법-------------------

def fibo(n):
    return fibo(n-1) + fibo(n-2) if n >= 2 else n

for n in range(1, 11):
    print(n, fibo(n))

def fibo(n):
    if n < 2:
        return n

    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a + b

    return b


for n in range(1, 11):
    print(n, fibo(n))

출처: https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95.html

 

 

감사합니다. Thank you!