[알고리즘] 재귀함수

🍀재귀함수

기본적으로 자주 사용되는 재귀함수에 대한 정리

😐알아둘 것

1. 재귀호출은 종료조건을 명시하지 않을 경우 무한루프에 빠지기 때문에 재귀함수 생성시 꼭 종료조건부터 명시할 것

2. 재귀의 순환이 STACK처럼 쌓인다고 생각하면 이해하기 쉬움

💻 예시

[팩토리얼]
10! = 10x9x8x7x6x5x4x3x2x1

class Solution {
    public int solution(String numbers) {
        System.out.println("factorial 10 : " + factorial(10));
        return 0;
    }
    
    public int factorial(int n){
        if(n<1) return 1;
        else{
            return n*factorial(n-1);
        }
    }
}

[피보나치 수열]

class Solution {
    public int solution(String numbers) {
        System.out.println("fibonacci 10 : " + fibonacci(10));
        return 0;
    }
    
    public int fibonacci(int n){
        if(n<=1) return n;
        else{
            return fibonacci(n-2) + fibonacci(n-1);
        }
    }
}

[동적계획법을 이용한 피보나치 수열]

class Solution {
   int[] fibo;
    
    public int solution(String numbers) {
        int n = 10;
        fibo = new int[n+1];
        int result = fibonacci(n);
        
        System.out.println(result);
        
        return 0;
    }
    
    public int fibonacci(int n){
        //계산된 식을 가지고 있는 경우 바로 리턴
        if(fibo[n] != 0) return fibo[n];
        if(n<=1) return n;
        
        fibo[n] = fibonacci(n-2) + fibonacci(n-1);
        
        return fibo[n];
    }
}