자료구조 및 알고리즘 요약정리 - 3

02-1-1 강의

초반 설명이라 생락

자료구조의 재귀구조는 하노이의 타워가 거의 최상위 난이도의 예제이다.

 

02-1-2 강의

1.

재귀호출: 함수내에서 함수자신을 다시 호출하는것

-> 함수에서 재귀하는 것은 함수 처음으로 재진입하는 것 보다는 함수를 복사하여 그것을 호출한 것이다.(즉, 함수를 새로 호출한 것이다. 53.p의 ☆참조)

ex) A-호출->B-호출->C-호출->D : 이 경우 D가 종료되어야 C가 종료될수있음.(C는 B가, B는 A가)

 

*재귀함수 작성시 탈출조건이 필요하다(그렇지 않으면 스택의 용량이 차고 결국 오버플로우가 된다.)

 

2.

재귀는 수학으로 이해하자. 예를 들어 n! (=n*(n-1)*(n-2)*.....*2*1, n개의 물건을 순서대로 나열하는 경우의수)을 수식적으로 나타내면

이를 함수로 표현하면

함수이름 AA

 

if(n>=1)

{

return n*AA(n-1);

}

else    //n==0일때

{

return 1;

}

 

※ 0!=1이다.

 

02-2-1 강의

1.

함수 구성시 '호출관계와 호출순서'를 이해해야 된다.

호출관계: 누가 누구를 호출하는가

호출순서: 호출관계에서, 실제로 실행시 실행 및 호출되는 함수의 순서

=> 하지만 재귀에서는 호출순서를 알기힘들다.

ex) 재귀함수를 코드로 구현 -> 호출관계 구현

      코드를 거꾸로 들어가며 순서 추적 -> 호출순서 추적 -> 추적하기 힘들다.

 

※ 재귀함수 구현하기

문제 -> 논리적설계 -> code구현 -> code내 함수간 호출관계 표현(이해)

 

2. 피보나치 수열

정의: 앞 2개의 숫자를 더해 현재의 수를 만들어가는 수열(처음 두개의 수는 0과 1)

수식:

 

코드구현:

int f(int n)

{

if(n==1)

return 0;

else if(n==2)

return 1;

else

return f(n-1)+f(n-2);

}

 

* 코드의 실행 흐름을 살펴보기: 58.p~59.p코드 참조

이를 그림으로 나타내면 트리구조로 나온다.(60.p참조)

 

02-2-2 강의

1. 이진 탐색 알고리즘의 재귀적 구현

① 입력받을 매개변수 선정

② 탈출조건 선정 -> ☆

③ 탈출-중앙값-비교-반복의 구조구현

 

=> 앞의 이진탐색알고리즘(반복문)과 지금의 이진탐색알고리즘(재귀호출)을 비교해보자

 

2. 재귀 구조 함수의 특징

장점

수학적으로 만들어진 알고리즘을 빠르게 구현가능(직관적)

가독성을 확보할 수 있고, 정확한 동작하는 것을 증명하기 쉽다(직관적이니까)

변수 사용을 줄일 수 있다.

 

단점

자원(스택)이 한정되어 있으면 오버플로우가 일어날 수 있다.

반복문(for나 while같은 루프)에 비해 느리다.

 

※ 꼬리재귀(=tail recursion=tail call)를 사용할 경우 스택사용을 줄일수 있다.

 

※ 참고사이트: https://kldp.org/node/134556