알고리즘 - 재귀

함수가 자기 자신을 호출하는 것.

복잡한 내용을 단순하게 만드는 함수.

구조 - 재귀 단계

기본 단계 Basic_Case

• 재귀 함수가 계속 호출되지 않고 종료되는 시점

재귀 단계 Recursive Case

• 함수가 자기 자신을 호출하는 단계
• 함수의 입력이 점점 작아지는 패턴을 가져야 함

예시

1. 팩토리얼

• 양의 정수 N에 대해 1부터 n까지 모든 정수를 곱한 값.

package 재귀.순조부;

import java.io.*;

public class Factorial {
    public static void main(String[] args) throws IOException {

        System.out.println(fatorial(5));
    }
    public static int fatorial(int n) {
        if (n == 0) {
            return 1;
        } else {
            return n * fatorial(n - 1);
        }
    }
}

2. N까지의 자연수의 합

package 재귀.순조부;

import java.io.*;

public class Sum_num {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int target_num = Integer.parseInt(br.readLine());

        //basis Part
        System.out.println(reculsive_sum(target_num));
    }

       //recursive Part
    public static int reculsive_sum(int target_num) {
        if (target_num == 1) {
            return 1;
        } else {
            return target_num + reculsive_sum(target_num - 1);
        }
    }

}

피보나치

package 재귀.순조부;

import java.io.*;

public class Fibonacci {

    public static int fibonacci(int target_num) {
        if (target_num == 0) {
            return 0;
        }

        if (target_num == 1) {
            return 1;
        }

        //Reculsive Part
        return fibonacci(target_num - 1) + fibonacci(target_num - 2);

    }
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int target_num = Integer.parseInt(br.readLine());

        int answer = fibonacci(target_num);
        System.out.println(answer);

    }
}