Python Basic 16 | 재귀호출 사용하기

재귀호출 사용하기

def hello(count):
    if count == 0:
        return
    print('Hello world', count)

    count -= 1
    hello(count)

hello(5)

• 결과 : Hello world 가 5번 출력된다. Hello world 5
  Hello world 4
  Hello world 3
  Hello world 2
  Hello world 1
  

이렇게 함수 안에서 자기 자신을 호출하는 것을 재귀호출이라고 한다.

재귀호출로 팩토리얼 구하기

def factorial(n):
    if n == 1:
        print(n)
        return 1

    return n * factorial(n - 1)

print(factorial(4))

재귀호출로 n-1 을 계속 전달하다가 n이 1일 때 1을 반환하면서 n과 곱하고 결괏값을 반환한다.

재귀호출로 회문 판별하기

def is_palindrome(word):
    print(word)
    if len(word) < 2:
        return True
    if word[0] != word[-1]:
        return False
    return is_palindrome(word[1:-1])

print(is_palindrome('hello'))  # False
print(is_palindrome('level'))  # False
print(is_palindrome('heryigjyreh'))  # False

재귀호출로 피보나치 수 구하기

문제

표준 입력으로 정수 한 개가 입력됩니다(입력 값의 범위는 10~30). 다음 소스 코드를 완성하여 입력된 정수에 해당하는 피보나치 수가 출력되게 만드세요.

피보나치 수는 0과 1로 시작하며, 다음 번 피보나치 수는 바로 앞의 두 피보나치 수의 합입니다.

입력(n)

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21...

출력

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946...

def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)