재귀호출

1. 알고리즘이란?

• 알고리즘 : 계산을(컴퓨터를) 통하여 문제를 해결하는 방법
• 의사코드 : 문제를 해결하고자 하는 방법과 의도를 표한 코드
• 알고리즘의 성질
  1.유한성 : 유한한 횟수를 거치고 종료되어야함. 즉, 무한루프는 알고리즘이 아니다.
  2.명확성 : 알고리즘의 각 단계가 명확해야함.
  3.입력 : 0개 이상
  4.출력 : 1개 이상
  5.효과성 : 알고리즘은 시,공간적 효율이 있어야하며 의미가 있어야함.

2. 재귀호출

• 재귀호출이란? : 함수가 자기자신을 호출 그러나 왜?
  변수를 여러개 만들 필요X 코드가 간결해진다는 장점이 있음.

• 재귀함수와 반복문의 장단점
  

재귀함수를 사용하면 지속적으로 함수를 호출하게 되는데,
이 때 사용하는 매개변수, 지역변수, 리턴 값, 그리고 함수 종료 후 돌아가는 위치등을 지속적으로 프로세스의 Stack에 저장해야한다.
이는 선언한 변수의 값만 변경해서 사용하는 반복문과 달리 많은 메모리 사용을 의미한다.
또, 함수 호출과 복귀를 하기 위한 context switching 비용이 발생하기 때문에, 속도가 상대적으로 느리다.
즉, 오버헤드가 발생하여 속도가 느리게 된다.

3. 수학적 귀납법

• 재귀호출과 비슷한 수학적 귀납법 == 재귀적 증명법

• 수학적 귀납법 멍제 P(n)을 다음과 같이 증명하는 방법
  1.N=1일 때 성립함을 보인다.
  2.P(k)가 성립한다고 가정할 때, P(k+1)이 성립합을 보인다.
  3.따라서 모든 자연수 n에 대하여 P(n)이 성립한다.

• 수학적 귀납법의 진짜 의미는 재귀적으로 증명이 가능해야함.
  즉, 6일때 증명했던 방법을 5일때 증명하고... 계속

• 재귀호출 = 재귀적 계산법

• 코드를 일일이 따라가지 않고 그냥 코드만 보고 아 이것은 옳게 반환한는 코드이다를 알아야함.

4. 퀵 정렬

• 재귀호출을 사용하는 대표적인 예제
• 자세한 것은 alice 알고리즘 문제로..

5. 재귀함수 디자인

• 재귀함수를 디자인하기 위한 세가지 단계
  1.함수의 정의를 명확히 한다. == 명확한 명제
  2.기저조건(base condition)에서 함수가 제대로 동작하게 작성한다. == n이 1일때 동작한는지?
  3.함수가 작은 input에 대하여 제대로 동작한다고 가정하고 함수를 완성한다. == n-1이 잘 동작한다고 가정한다.

6. 요약

• 알고리즘 : 문제를 해결하는 방법
• 재귀호출은 알고리즘에서 매우 중요하다.