[코드트리 조별과제] 재귀함수

코딩테스트에 감이 떨어지기도 하고, 코테를 꾸준하게 도전하기 위해 코드트리 조별과제에 참여하게 되었다.

내가 스스로 공부한 것을 조별과제에 참여할 겸, 기록에 남기기위해 정리하려고한다. 

 

재귀함수

---

함수 f가 해당 함수를 구현하는 데 동일한 함수 f를 다시 이용하게 되는 것을 재귀함수 라고 부릅니다.

재귀함수의 중요한 조건은 종료조건이다. 종료 조건을 적절하게 설정해줘야만, 재귀 함수는 올바르게 동작하게 된다.

 

1. 값을 반환하지 않는 재귀함수
2. 값을 반환하는 재귀함수

 

이렇게 2가지로 나눌 수 있다. 

 

 

 

 

1. 값을 반환하지 않는 재귀함수

 

값을 반환하지 않는 재귀함수의 대표적인 문제는 반복 출력하기 이다.

https://www.codetree.ai/missions/5/problems/repeated-output-2/introduction

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

import java.io.*;

public class Main {
    public static void print(int N) {
        if (N == 0) return;
        else {
            N--;
            System.out.println("HelloWorld");
            print(N);
        }
    }
    public static void main(String[] args) throws Exception {
        // 여기에 코드를 작성해주세요.
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        print(N);
    }
}

 

값을 반환하지 않고, return문을 이용하여 재귀함수의 종료조건을 나타내주었다.

 

 

2. 값을 반환하는 재귀함수

1부터 n까지의 곱을 반환하는 팩토리얼 함수가 값을 반환하는 재귀함수의 유형 중 가장 대표적인 유형이다.

재귀함수에서의 종료조건은 지극히 자명한, 계산 없이도 바로 결과를 알 수 있는 경우 로 설정하는 것이 대부분이다.

 

https://www.codetree.ai/missions/5/problems/sum-from-1-to-a-certain-number-2/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

import java.util.Scanner;

public class Main {
    public static int sum(int n) { 
        if(n == 0)                          
            return 0;

        return sum(n - 1) + n;
    }

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

        // 변수 선언 및 입력:
        int n = sc.nextInt();

        System.out.println(sum(n));
	}
}

 

n = 0일 땐 0이라는 사실이 지극한 계산결과이기 때문에 이렇게 구현해주어야한다.