[Java] 재귀함수 | 인프런 | 재귀문제

문제

자연수 N을 입력하면 재귀함수를 이용하여 1부터 N까지를 출력하는 프로그램을 작성하세요 

 

풀이

재귀 함수를 이용해서 1부터 N까지 출력하면 문제를 해결할 수 있습니다.

재귀함수는 함수의 정의 안에서 다시 자기 자신(함수)을 사용합니다. 예를 들면 다음과 같습니다. f(n) = f(n-1) + 1. 

재귀함수는 계속해서 자기 자신을 호출합니다. 그렇기 때문에 탈출 조건을 작성하지 않으면 무한루프에 빠져 스택오버플로우가 발생합니다. 스택에 저장된 호출함수의 정보가 끊임없이 생성되어 stack(스택에는 각 호출(스택프레임)마다 복귀주소, 지역변수, 매개변수가 누적됩니다)이 넘치기 때문입니다. 그렇기 때문에 재귀함수는 반드시 탈출조건을 작성해야 합니다.

 

 

 

재귀함수는 크게 다음과 같은 if-else 구조를 가집니다. 재귀 문제를 풀 때에는 다음과 같은 구조를 미리 만들면 쉽게 풀 수 있습니다.

// 재귀함수
public void f(int n) {
	if(탈출조건){	// 탈출 구간
	...
	}
	else {	// 다시 f를 호출하는 구간
	...
	}
}

 

 

소스코드

import java.util.Scanner;

/*
* f(n) = f(n-1) + 1;
* 재귀함수 함수를 정의할 때 자기 자신을 다시 사용하는 함수.
* */
public class Main {
    public static void recursion(int n) {
        if (n == 0) return ;
        else {
            recursion(n-1);
            System.out.print(n + " ");
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        recursion(n);
    }
}

rucursion(n-1)과 System.out.print(n + " ")문의 순서에 주의합니다. 문제처럼 오름차순으로 출력하려면 1이 먼저 출력되어야 하니깐 함수호출이 먼저 와야 합니다. 만약, 내림차순으로 만들고 싶다면 출력문이 먼저 오면 됩니다.