자바 기초 3 (반복 함수와 재귀 함수)

반복 함수 : while 문, for 문

재귀 함수 

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

즉 함수 안에 자기 자신이 또 들어가 있는 형태

 

어떠한 수를 소환 했을 때 타고 들어가서 가장 작은 단위로 들어간 다음에

가장 작은 단위가 해결되고 나면 그 값을 거슬러 올라가 반환하여 답을 도출

 

팩토리얼을 재귀 함수로 구현

public class Main {   public static int factorial (int number) {     if (number == 1)           return 1;     else           return number * factorial(number - 1);     }     /* number이 1이면 1을 반환해주고     1이 아니라면 number에 자기 자신에 1을 뺀 값을 곱해줌     5! = 5 * 4!     5! = 5 * 4 * 3!     5! = 5 * 4 * 3 * 2!     5! = 5 * 4 * 3 * 2 * 1     */        public static void main(String[] args) {     System.out.println("10 팩토리얼은 " + factorial(10));        } }

 

팩토리얼을 반복 함수로 구현

public class Main {   public static int factorial (int number) {     int sum = 1;     for (int i = 2; i <= number; i++){       sum *= i;     }     // 5가 될 때 까지 반복적으로 1씩 증가하면서 sum에 곱해줌     return sum;   }        public static void main(String[] args) {     System.out.println("10 팩토리얼은 " + factorial(10));        } }

 

피보나치 수열

1 1 2 3 5 8 ...

(이전 두 값을 더해서 진행하기)

 

 

피보나치 수열을 재귀 함수로 구현

- 몇 번째 해당하는 값이 어떤 값을 가지는지 맞히기

public class Main {   public static int fibonacci (int number) {     if (number == 1){       return 1;     }     else if (number ==2){       return 1;     }     else {       return fibonacci(number - 1) + fibonacci(number - 2);       // 피보나치 수열은 한칸 전의 값과 두칸 전의 값을 더한 것     }   }        public static void main(String[] args) {     System.out.println ("피보나치 수열의 10번째 원소는 " + fibonacci(10) + "입니다.");   } }

 

피보나치 수열을 반복 함수로 구현

public class Main {   public static int fibonacci (int number) {     int one = 1;     int two = 1;     int result = -1;     // -1은 문제가 발생했을때의 반환값     if (number == 1){       return one;     }     else if (number == 2){       return two;     }     else {       for (int i = 2; i < number; i++){         result = one + two;         one = two;         two = result;         // 힌칸씩 one, two를 옮기기       }     }     return result;   }        public static void main(String[] args) {     System.out.println ("피보나치 수열의 10번째 원소는 " + fibonacci(10) + "입니다.");   } }

 

재귀함수의 문제

: 특정한 연산이 지속적으로 반복된다.

계산 해야하는 연산이 기하급수적으로 많아진다. -> 시간이 오래 걸림

때에 따라서는 반복이 나을 수도 있다.