[알고리즘] 재귀(Recursion)

 

📒 반복(Iteration)과 재귀(Recursion)

• 반복과 재귀는 유사한 작업을 수행할 수 있다
• 반복은 수행하는 작업이 완료될 때까지 계속 반복
  • 루프 (for/while, do~while 구조)
• 재귀는 주어진 문제의 해를 구하기 위해 동일하면서 더 작은 문제의 해를 이용하는 방법
  • 어떠한 개념이나 문제에 대한 정의를 그 개념이나 문제를 포함하는 작은 개념이나 문제로 나타내고 그 작은 개념, 부문 문제들에 동일하게 적용
    • 더 이상 작은 개념 부분 문제가 없을 때 ⇒ 재귀의 끝
  • 하나의 큰 문제를 해결할 수 있는 (해결하기 쉬운) 더 작은 문제로 쪼개고 결과들을 결합한다
  • 재귀 함수로 구현

 

📒 재귀 함수 (recursive function)

함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수

• 일반적으로 재귀적 정의를 이용해서 재귀 함수를 구현한다
• 따라서 기본 부분(basis part, 기저조건(재귀 끝))와 유도 부분(inductive part, 재귀 파생)으로 구성된다
• 재귀적 프로그램을 작성하는 것은 반복 구조에 비해 간결하고 이해하기 쉽다
  • 그러나 재귀에 대해 익숙하지 않은 개발자들은 재귀적 프로그램이 어렵다고 느낀다
• 함수 호출은 프로그램 메모리 구조에서 스택을 사용한다
• 따라서 재귀 호출은 반복적은 스택의 사용을 의미하며 메모리 및 속도에서 성능저하가 발생한다

 

✏️ 재귀 함수 구현

➡️ 설계할 때 생각해봐야 할 것

1. 함수에 대한 정의(역할)을 명확히!
2. 함수 수행에 필요한 결정적 요인, 값 설계 ⇒ 매개변수
3. 재귀 종료 조건 따지기

 

➡️ 재귀 함수 구성 요소

1. 기저 조건(종료 조건)
2. 전처리 로직 (재귀 호출 전에 처리되어야 하는 로직)
3. 재귀 호출
4. 후처리 로직

 

✏️ 피보나치 수열

• 이전의 두 수 합을 다음 항으로 하는 수열
• 피보나치 수열의 i번째 값을 계산하는 함수 F

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