[ BASIC MATH ] 05. 점화식과 재귀함수

[ BASIC MATH ] 05. 점화식과 재귀함수

 

 

 

 

📚 Table of Contents

 

 

 

 

점화식 ( Recurrence )

 

점화식 이란?

 

수열의 각 항 간에 관계를, 간단하게 표현하는 관계식 ( 단순 나열이 아닌 규칙으로 )

• 수열의 N번째 항을,
• 그 앞의 항들에 의해, ( 그보다 작은 항에 의해 )
• 규칙적 ( 종속적 )으로 표현한 관계식
  
  
  

📒 예시

{an} : 1, 3, 5, 7, 9.....
a1 = 1
an+1 = an + 2

 

 

 

 

점화식 특징

 

• 점화식의 구성 형태
  • 등식 또는 관계식 형태를 갖춘다.
    • 단, 문제 제시 때는, 초기갑 또는 경곗값이 반드시 필요하다
• 점화식이 주는 정보
  • 점화식 자체는 ,간접적이고 부분적인 정보만 준다,
  • 따라서, 일반항을 구할 필요가 있다.
    
    
• 점화식을 풀기
  • 수열의 일반항(general term)을 구하는 것
    • 대부분, 수열의 초기값과 점화식을 이용하여 일반항(점화식 해)을 구할 수 있으나,
    • 수열의 일반항을 구할 수 없거나, 적절한 점화식으로 표현 못하는 경우도 많다
  • 수열의 일반항을 구하는 일반화된 방법은 => 생성 함수에 의한다.
    
    
• 점화식의 해 : 일반항
  • 점화관계를 만족시키는 닫힌 형식의 수열 공식이다
    
    
• 점화식의 응용
  • 주로, 수열의 재귀적 정의에 이용된다.
    
    

 

 

 

 

재귀함수

 

재귀적 / 순환적 ( recursive ) 란?

 

자기 자신을 이용하여 정의하거나 응용하는 것

 

 

 

재귀 함수란?

 

• 호출된 함수가 다시 자기자신을 호출하는 것
  • 자기 자신을 이용하여 정의시켜 놓고, 반복적으로 스스로를 호출/사용하는 함수 
    
    
• 용도
  • 통상, 문제 내 작은 형태의 문제가 연이어 포함된 내포구조의 프로그래밍에 적합하다.
    • 자기 자신을 다시 호출하여 문제를 푸는 방법을 쓴다
  • 마치 루프처럼 어떤 일을 반복적으로 수행하는 데에 유리하다.
  • 트리 및 연결 리스트와 같은 자료구조에 유용하다.
    
    
• 재귀 호출의 복귀시 : 스택 자료구조를 활용하여 복귀한다.
  
  
  

 

 

 

 

재귀 함수의 요건

 

1. 종료 조건 ( stoppig condition ), 기저 조건 ( base case )
   • 재귀적 호출에서 빠져나오는 탈출 조건
   • 충분히 작아진 문제(종료 조건)에서, 직접 해결하고, 그 결과를 바로 윗선에 반환한다.

2. 재귀 호출 ( recursive case )
   • 각 단계 마다, 종료 조건에 접근하도록 그 자신을 재귀적으로 호출하게 된다.
   • 원래 문제 보다 작아진 부분 문제를 대상으로 한다.

 

 

 

 

재귀문 vs 반복문

 

재귀문은 반복문으로도 프로그래밍 구현이 가능하다.

 

하지만 재귀는 반복보다 훨씬 명확하고 간결하게 표현가능하다.

 

결국, 프로그래밍 용이성 및 메모리 소요 크기로써 이 둘 중에 선택이 필요하다.

 

 

 

 

예제

[ BASIC MATH ] 05. 점화식과 재귀함수 with java

 

 

 

 

reference

점화식