[JAVA] 알고리즘 문제풀이 기초 - Recursive (재귀함수)

Recursive (재귀함수)

재귀함수1

설명 : 자연수 N이 입력되면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요.
입력 : 첫 줄은 정수 N(3<=N<=10)이 입력된다.
출력 : 첫 번째 줄에 출력하세요.
풀이 답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();

        t.solution(num);

    }

    public void solution(int num){

        if(num==0) return;

        solution(num-1);
        System.out.print(num+" ");
    }
}

정리
1. 재귀함수의 기본 개념을 테스트하는 문제

재귀함수(이진수 변환)

설명 : 10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램을 작성하세요. 단 재귀함수를 이용해서 출력해야 합니다.
입력 : 첫 번째 줄에 10진수 N(1<=N<=1,000)이 주어집니다.
출력 : 첫 번째 줄에 이진수를 출력하세요.
풀이 답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();

        t.solution(num);
    }

    public void solution(int num){

        if(num<=0) return;

        solution(num/2);
        System.out.print(num%2);
    }
}

정리
1. 재귀함수의 기본 개념을 테스트하는 문제
2. 계속해서 절반의 값으로 실행하되 0이하의 값이 나오면 return

재귀함수(팩토리얼)

설명 : 자연수 N이 입력되면 N!를 구하는 프로그램을 작성하세요.
입력 : 첫 번째 줄에 자연수 N(1<=N<=100)이 주어집니다.
출력 : 첫 번째 줄에 N팩토리얼 값을 출력합니다.
풀이 답안

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();

        System.out.println(t.solution(num));
    }

    public int solution(int num){

        if(num==1) return num;

        int mul = solution(num-1);
        return num*mul;
    }
}

정리
1. 재귀함수의 기본 개념을 테스트하는 문제
2. 계속해서 하위 숫자를 곱해 나가는 방식

재귀함수(피보나치)

설명 : 피보나치 수열을 출력한다. 피보나치 수열이란 앞의 2개의 수를 합하여 다음 숫자가 되는 수열이다. 입력은 피보나치 수열의 총 항의 수 이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다.
입력 : 첫 줄에 총 항수 N(3<=N<=45)이 입력된다.
출력 : 첫 줄에 피보나치 수열을 출력합니다.
풀이 답안 (반복문 사용)

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int size = scan.nextInt();
        int[] arr = new int[size];

        for (int i : t.solution(arr, size)) {
            System.out.print(i+" ");
        }
    }

    public int[] solution(int[] arr, int size){

        for(int i=0; i<size; i++){
            if (i<2) arr[i]=1;
            else arr[i] = arr[i-1]+arr[i-2];
        }
        return arr;
    }
}

풀이 답안 (재귀함수 사용)

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Main t = new Main();
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();

        for(int i=1; i<=num; i++){
            System.out.print(t.solution(i)+" ");
        }
    }

    public int solution(int num){

        if(num==1) return 1;
        if(num==2) return 1;
        else return solution(num-1)+solution(num-2);
    }
}

개선 답안 (재귀함수 사용+static 배열) ``` java import java.util.*;

public class Main {

static int[] arr;

public static void main(String[] args) {
    Main t = new Main();
    Scanner scan = new Scanner(System.in);
    int num = scan.nextInt();
    arr=new int[num+1];
    t.solution(num);

    for(int i=1; i<=num; i++){
        System.out.print(arr[i]+" ");
    }
}

public int solution(int num){

    if(arr[num]!=0) return arr[num];

    if(num==1) return arr[num]=1;
    if(num==2) return arr[num]=1;
    else return arr[num]=solution(num-1)+solution(num-2);
} } ```

정리
1. 반복문을 사용하지 않고 재귀함수를 사용해서도 구현 가능 (다만 스택메모리를 사용해야해서 효율의 문제는 전자가 낫지않을까 생각)
2. 배열을 사용하지않고 n-1, n-2를 매개변수로 사용해 재귀변수를 반복해서 돌아 계산할 수 있음
3. 재귀를 반복해서 도는것보다는 static 배열을 만들고 값을 담아 처리하는것이 훨씬 효율적임

IM

Recursive (재귀함수)

재귀함수1

재귀함수(이진수 변환)

재귀함수(팩토리얼)

재귀함수(피보나치)