자료구조 - Chapter 02

재귀 (ReCursion)

재귀 함수

함수 내에서 자기 자신을 다시 호출하는 함수

함수가 호출되면 자기 자신이 복사되어 실행한다고 생각하면 이해하기 편하다.

재귀 함수를 정의하는데 있어서 탈출 조건을 구성하는 것이 중요하다.

 

예제 : 간단한 재귀함수 예시

 

재귀로 함수 호출을 계산하는 함수

ex1_1 Recursive Ex.c

0.00MB

if (num <= 0) 을 통하여 함수 탈출 조건을 명시한다.

 

예제 : Factorial 재귀함수로 구현하기

F(n) = n * F(n - 1)  -- (n>= 1)

         1 -- (n = 0) 탈출 조건으로 선택

factorial 재귀함수

ex1_2 Factorial.c

0.00MB

if (n == 0) 탈출 조건을 명시한다.

 

예제 : 피보나치 수열 재귀함수로 구현하기

         0  -- n = 1 탈출 조건

F(n) = 1  -- n = 2 탈출 조건

         F(n - 1) + F(n - 2) -- 그외

피보나치 수열 재귀함수

ex2_1 Fibonacci.c

0.00MB

식 그대로 코딩으로 구현하면 된다.

만약 좌우 재귀함수가 return으로 반환되는 경우

왼편의 Fibo함수 먼저 호출이 완료 되어야 오른쪽 Fibo 함수가 호출이된다.

그 과정을 트리로 구현해서 확인하면 편리하다.

ex2_2 Fibonacci funcCall.c

0.00MB

 

예제 : 이진 탐색 알고리즘 재귀 구현

재귀함수 구현시, 2가지를 생각하는게 편하다.

• 일련의 반복적인 과정
• 탈촐조건

이진 탐색 알고리즘을 재귀로 구현할 때 고려할 점은

• 탐색 범위 중앙 확인, 없다면 반으로 줄여서 다시 확인
• 탐색 시작 위치가 탐색 범위 끝 보다 커지는 경우

이진 탐색 재귀 구현

ex2_3 Binary SearchRecur.c

0.00MB

예제 : 하노이 탑 (The Tower of Hanoi)

하노이탑 문제 접근

• 작은 원반 n - 1개를 A -> B로 이동
• 큰 원반 1개를 A에서 C로 이동
• 작은 원반 n - 1개를 B에서 C로 이동

하노이탑 재귀함수

ex3 Hanoi.c

0.00MB