Function call & Recursive Function (함수 호출 및 재귀 함수)

함수 호출 설명

• 프로그램에서의 함수 호출과 복귀에 따른 수행 순서를 관리
  • 가장 마지막에 호출된 함수가 가장 먼저 실행을 완료하고 복귀하는 후입선출 구조이므로, 후입선출 구조의 스택을 이용하여 수행순서 관리
  • 함수 호출이 발생하면 함수 수행에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소 등의 정보를 스택 프레임에 저장하여 시스템 스택에 삽입
  • 함수의 실행이 끝나면 시스템 스택의 top 원소(스택 프레임)를 삭제(pop)하면서 프레임에 저장되어 있던 복귀주소를 확인하고 복귀
  • 함수 호출과 복귀에 따라 이 과정을 반복하여 전체 프로그램 수행이 종료되면 시스템 스택은 공백 스택이 됨
• 함수 호출과 복귀에 따른 전체 프로그램의 수행 순서

재귀호출 설명

• 자기 자신을 호출하여 순환 수행되는 것
• 함수에서 실행해야 하는 작업의 특성에 따라 일반적인 호출방식보다 재귀호출방식을 사용하여 함수를 만들면 프로그램의 크기를 줄이고 간단하게 작성

---

• 대표적 예시 : 팩토리얼

  n! = n * (n-1)!
  (n-1)! = (n-1) * (n-2)!
  (n-2)! = (n-2) * (n-3)!
  ...
  2! = 2 * 1!
  1! = 1

• factorial 함수에서 n=4 인 경우의 실행

---

• 대표적 예시: 피보나치 수열

  • 0과 1로 시작하고 이전의 두 수 합을 다음 항으로 하는 수욜을 피보나치라 함

    0, 1, 2, 3, 5, 8, 13, ...

• 피보나치 수열의 i번째 값을 계산하는 함수 F를 정의 다음의 형태

  • F0 = 0, F1 = 1
  • Fi = Fi-1 + Fi-2 for i >= 2
• 위의 정의로부터 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현 가능

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