[자바 기초 프로그래밍] 반복함수와 재귀함수

반복함수와 재귀함수

Java Programming Tutorial 2017 by 나동빈

링크 : https://youtu.be/2fsJ6Hlcfs4

 

 

반복함수를 이용해서 팩토리얼 구현

public class Main {

    public static int factorial(int number) {
        int sum = 1;
        for(int i = 2; i <= number; i++)
        {
            sum *= i;
        }
        return sum;
    }

    public static void main(String[] args) {

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

 

 

재귀함수를 사용해서 팩토리얼 구현

public class Main {

    public static int factorial(int number) {
        if(number == 1)
            return 1;
        else
            return number * factorial(number - 1);
        // 5! = 5 * 4!
    }

    public static void main(String[] args) {

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

}

 

 

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

public class Main {

    public static int fibonacci(int number) {
        int one = 1;
        int two = 2;
        int result = -1;    // 문제가 발생했을 때의 반환 값
        if(number == 1)
        {
            return one;
        }
        else if(number == 2)
        {
            return two;
        }
        else
        {
            result = one + two;
            one = two;
            two = result;
        }
        return result;
    }


    public static void main(String[] args) {

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

 

 

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

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("피보나치 수열의 5번째 원소는 " + fibonacci(50) + "입니다.");
    }
}

• 반복함수와 달리 재귀함수를 사용할 경우 반복되는 계산을 여러번 요구할 수 있다
  • 숫자가 커지면 커질수록 기하급수적으로 많아짐
  • 이를 대체하기 위해 동적 프로그래밍을 사용할 수 있다