[알고리즘] 4. 재귀함수

1. 재귀함수

자기자신을 부르는 함수

1.2 재귀함수가 의미있는 예제

• 펙토리얼 n! = n(n-1)(n-2)…*1

  1 2 3 4

  int getFactorial(int n){ if(n==1) return 1; else return n*getFactorial(n-1); }

함수 호출 흐름

1. main에서 getFactorial(3) 호출된다고 가정.
2. getFactorial(3)에서
   3*getFactorial(2)리턴
3. getFactorial(2)에서
   2*getFactorial(1) 리턴
4. getFactorial(1)에서 1리턴
5. 123 도출

1.2 두가지 계산반벙

1.2.1 순차적 계산방법

A를 계산, A를 이용해서 B를 계산, B를 이용해서 C를 계산..
n!=n(n-1)…1

1.2.2 귀납적 계산방법

구하려고 하는 값은 f(x) f(x)를 구하기 위해 또 f(x)를 활용함
n!= 5f(4)
n!=54f(3)
…
n! = 5432*f(1)

• n의 m제곱을 귀납적으로 정의
  n^m = nn^(m-1)
  …
  n^m = nnn..n^0

1.3 수납적 귀납법

명제 p(n)이 모든 n에 성립함을 증명.
p(k)가 성립한다고 가정후 p(k+1)이 성립함을 증명.

2 재귀함수 디자인

2.1 3가지 절차

1) 함수의 역할을 명확하게 정의

2) 기저조건에서 함수가 제대로 동작함을 보임

3) 함수가 제대로 동작한다고 가정하고 함수를 완성

2.2 재귀함수 구현

2.2.1 n의 m제곱

1) getPower(n,m)은 n의 m승을 반환하는 함수이다.

ex) getPower(2,4)=16

2) 기저조건 getPower(n,0)=1

3) getPower(n,m)=n * getPower(n, m-1)

2.2.2 이진수 출력하기

1) pringBin(x)는 X를 이진수로 바꿔출력하는 함수

2) 기저조건 printBin(1)=1, printBin(0)=0

3) printBin(x)={ print(x/2); print(x%2);}

2.2.3 펠린드롬인지 판별하기

• 펠린드롬은 좌우 대칭인 값을 말함

  1) isPal(String, start, end)

  2) 기저조건: start==end isPal(String, start, end)=true;

  3) isPal(String, start, end)

  if(String.start==String.end) return isPal(String, start+1, end-1);
  else return false;