10~11. 반복함수와 재귀함수(팩토리얼 / 피보나치 수열) ) [프로젝트명 : Tutorial10, 11]

9. 반복함수와 재귀함수(팩토리얼/ 피보나치 수열) ( Tutorial10, 11)

반복함수는 while 혹은 for문법을 이용해서 문제를 해결하는 함수다.

재귀함수는 자신의 함수 내부에서 자기 자신을 스스로 호출함으로써 재귀적으로 문제를 해결하는 함수다.

(Tutorial10)

[1] 반복함수로 팩토리얼을 구현해보자

1. int를 하나 받아서 int를 반환하는 팩토리얼 함수를 만들자.

 -  로컬 변수 sum에 1을 넣어 초기화 한 다음, for문을 통해서 sum에다가 2부터 i를 받은 숫자까지 곱해서 넣어주자.

//5! = 5 * 4 * 3 * 2 * 1

public static int factorial(int number) {

int sum = 1;

for ( int i = 2; i<=number ; i++) {

sum *= i;

}

return sum;

}

2. 메인함수에서 출력시켜보자

public static void main(String[] args) {

System.out.println("10팩토리얼은 "+factorial(10)+ "입니다.");

}

[2] 재귀함수로 팩토리얼을 구현해보자.

1. 받은 값이 1일 때만 예외적으로, 1을 return해서 마무리 짓는다. 

   왜냐하면, 속에 똑같은 매쏘드()가 들어가는데, -1씩 줄여서 대입할 것이기 때문에, 마지막 1은 바로 1을 리턴하도록 한다

   재귀함수는 계속 자신을 호출하므로, 마지막에는 상수로 마무리대응 해야한다.

2. return할 때, 받은 수 * 매쏘드( 받은수 -1 ); 을 반환해서, 받은수 -1 이 또 한바퀴 돌도록 한다. 1이 되면 그냥 1이 return되서 끝난다.

 - 핵심은 -1 씩 줄여가다가 마지막 종점 1에서는 재귀함수를 호출 안하고, 값 1을 반환해서 끝낸다.

 - 핵심은 5!  =  5 * 4!로 같으며, 팩토리얼 속에 또 -1의 팩토리얼이 담겨져 있으니까, 재귀함수로 표현 가능하다.

   f(5) = 5 * f(4)

//5! = 5 * 4!

public static int factorial(int number) {

if(number ==1)

return 1;

else

return number * factorial(number-1);

}

(Tutorial11)

[3] 반복함수로 피보나치 수열을 구현해보자.

 - 피보나치 수열은 연속된 두 수를 더해서 다음 수가 나오는 수열을 말한다.(// 1, 1, 2, 3, 5, 8, ...)

 - k번 째 수가 무엇인지 알아내는 함수를 만들 것이다.

1. 첫째항 1과 둘째항 1을 미리 선언해준다. 잘못된 경우에 -1을 반환하도록 result도 만들어준다.

  (피보나치수열은 초기항 a1, a2는 기본적으로 주어진다)

2.  if /else if 에다가는 첫째항, 둘째항이 입력되면 바로 반환하도록 만들고 / 나머지 3번째항 이상인 경우 else에다가  아래와 같이 코드를 작성해야한다.

- for문 2 <=  i < number 까지 돌면서,

<2부터 시작하는 이유는, number가 3이라고 가정해보면, i=2일때만 for문이 작동하므로 a1 + a2 만 계산한 a3가 리턴된다

  만약 number가 4라면, i=2일 때 다음계산을 위해, a2가 one에 / a3가 two에 들어가고, 마지막 i=3이면 a2+ a3 가 result에 담겨서 리턴되기 때문>

      i = 2 일때, 초기항 2개를 더해서 result에 넣어준다. (one + two)

      다음계산을 위해서,  one에다가는 오른쪽으로 한칸 옮겨지므로, two를 대입해준다

        two에다가는 오른족으로 한칸 옮겨지므로, one+two값인 result를 넣어준다.

      i = 3 일때, 미리 옮겨진 one 과 two를 더해서 result에 더한다. 그리고 오른쪽으로 한칸씩 one과 two를 옮긴 값을 대입해 놓는다.

 ...

i=number-1 일때, number항 직전 2개의 항인 one과 two를 더해서 result에 넣는다. 그리고 다음계산을 위해 오른쪽으로 옮겨놓지만 사용되진 않음.

public static int fibonacci(int number) {

int one=1;

int two=1;

int result = -1;

if(number == 1)

{

return one;

}

else if(number == 2) {

return two;

}

else{

for(int i = 2; i < number ; i++) {

result = one + two; // number 직전까지 아래에서 one과 two를 옮겨놓았다.

one = two; // 수열 오른쪽으로 한칸씩 다음 계산을 위해, 옮겨놓는 작업.

two = result;

}

return result;

}

}

3. 출력해보자.

public static void main(String[] args) {

System.out.println("피보나치 수열의 10번째 원소는 "+fibonacci(10)+"입니다.");

}

[4] 재귀함수로 피보나치 수열을 구현해보자. 훨씬 간단해진다.

 - 핵심은 n-1씩 해가면서, 줄여가는 것이다. 그리고 마지막 종점지에는 상수를 이용해서 리턴해줘야한다. 

 - 팩토리얼 함수와 차이점은 n-1뿐만 아니라 n-2도 있으니, 2개의 초기항이 존재해야한다. 

1. 첫번째, 2번째 항에 대해서는 if문으로 바로 return1을 해주자.

2. 3번재 이상부터는, return값에 f(n-2) + f(n-1)만 해주면 된다.

public static int fibonacci(int number) {

if(number ==1)

{

return 1;

}else if(number==2) {

return 1;

}else {

return fibonacci(number-2) + fibonacci(number-1) ;

}

}

*** 반복함수와 달리 재귀함수의 피보나치 수열은 f(49) 계산시, f(48) + f(47)이 계산되지만, 

     f(48)계산시에도 f(47) + f(46)이 계산되므로, 반복되는 계산이 기하급수적으로 많아 진다.

     재귀함수를 사용할 때, 훨씬 비효율적인 계산을 하므로, 주의해서 계산해야한다. 실제로 f(50)을 물어보면, 계산값이 안나온다.