스택 - 재귀호출

1. 재귀호출

• 자기 자신을 호출하여 순환 수행되는 것입니다.
• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성할 수 있습니다.
  • 재귀 호출의 예) factorial
    • n에 대한 factorial : 1부터 n까지의 모든 자연수를 곱하여 구하는 연산입니다
    • 마지막에 구한 하위 값을 이용하여 상위값을 구하는 작업을 반복합니다.

---

---

• 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열을 피보나치라고 합니다.
  • 0, 1, 1, 2, 3, 5, 8, 13
• 피보나치수열의 i번 째 값을 계산하는 함수 F를 정의하면 다음과 같습니다.
  • F₀ = 0, F₁ = 1
  • F_i = F_i-1 + F_i-2 for i ≥ 2
• 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현할 수 있습니다.

# 피보나치 수를 구하는 재귀함수
def fibo(n):
    if n < 2:
        return n
    else:
        return fibo(n-1) + fibo(n-2)