동블

그래프 뷰

재귀 연습1

6 min read

숫자 차례로 출력하기

문제

  • 첫 번째 재귀함수를 이용하여 1부터 N까지 숫자를 차례대로 출력하고, 두 번째 재귀함수를 이용하여 N부터 1까지 출력

포인트

  • 재귀호출 위치를 같게 함으로서 다른 파라미터 값을 넣을 수 있다.
  • 재귀호출 위치를 다르게 함으로서 같은 파라미터 값을 넣을 수 있다.

풀이1

  • 재귀호출 지점을 다르게 하기. 최초 입력 값이 같음.
  • asc(int cnt) 함수 : cnt0일때 return되고, 출력하기전 재귀호출하므로, 1부터 출력됨.
import java.util.*;
import java.io.*;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        asc(n);
        System.out.println();
        desc(n);
    }
 
    static void asc(int cnt){
        if(cnt==0) return;
 
        asc(cnt-1);
 
        System.out.print(cnt+" ");
    }
    static void desc(int cnt){
        if(cnt==0) return;
 
        System.out.print(cnt+" ");
 
        desc(cnt-1);
    }
}

풀이2

  • 재귀 호출 이전 출력하기. 최초 입력 값이 달라짐.
import java.util.*;
import java.io.*;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        asc(1);
        System.out.println();
        desc(n);
    }
 
    static void asc(int cnt){
        if(cnt==n+1) return;
 
        System.out.print(cnt+" ");
 
        asc(cnt+1);
    }
    static void desc(int cnt){
        if(cnt==0) return;
 
        System.out.print(cnt+" ");
 
        desc(cnt-1);
    }
}
재귀함수의 꽃

문제

  • N이 주어질때, 재귀함수를 단 하나만 이용하여, 아래와 같이 출력.
  • N에서 1까지 1씩 감소하며 하나씩 출력했다가, 다시 1부터 N까지 1씩 증가하며 출력
  • N N−1 N−2 N−3 … 2 1 1 2 … N−1 N

풀이

  • 재귀를 단순히 ‘함수 호출’ 로 생각하지말고,
  • 현재 함수 실행을 잠깐 멈춰두고, 더 작은 함수를 끝까지 실행한 뒤, 다시 원래 위치로 돌아오는 것 으로 이해하자.
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        print(n);
    }
 
    static void print(int cnt){
        if(cnt==0) return;
 
        System.out.print(cnt +" ");
        print(cnt-1);
        System.out.print(cnt +" ");
        
    }
}

n=3을 예로 들면

print(3)
  3 출력
  print(2)
    2 출력
    print(1)
      1 출력
      print(0)
        return
      1 출력
    2 출력
  3 출력
별 출력

문제

  • n을 입력받아 예시와 같은 형태로 출력 예시: n=5
* * * * * 
* * * * 
* * * 
* * 
* 
* 
* * 
* * * 
* * * * 
* * * * *

풀이

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
 
        print(n);
        return;
    }
 
    static void print(int cnt){
        if(cnt==0) return;
        for(int i = 0 ; i < cnt ; i++){
            System.out.print("* ");
        }
        System.out.println();
        print(cnt-1);
        for(int i = 0 ; i < cnt ; i++){
            System.out.print("* ");
        }
        System.out.println();
    }
}
1부터 N까지의 합

문제

  • 1~N까지의 합

풀이

import java.util.*;
import java.io.*;
public class Main {
    static int sum,n;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        sum = recur(1);
 
        System.out.println(sum);
    }
 
    static int recur(int num){
        if(num==n) return n;
        return num + recur(num+1);
    }
}
각 자리 숫자의 제곱

문제

  • 8자리 이하의 정수 N에 대해 각 자리 숫자의 제곱의 합

풀이

import java.util.*;
import java.io.*;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        int ans = recur(n);
 
        System.out.println(ans);
    }
 
    static int recur(int num){
        if(num == 0) return 0;
        return (int)Math.pow(num % 10,2) + recur(num/10);
    }
}
피보나치

문제

  • 재귀 함수로 피보나치 수열을 작성하고 n번째 항의 값을 출력
  • 1, 1, 2, 5, 8, …

풀이

import java.util.*;
import java.io.*;
public class Main {
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
 
        int ans = fib(n);
        System.out.println(ans);
 
    }
 
    static int fib(int num){
        if(num == 1 || num == 2){
            return 1;
        } 
        return fib(num-1) + fib(num-2);
    }
}
배열의 최대값

문제

  • 정수 배열의 최댓값을 재귀함수로 구현

풀이

import java.util.*;
import java.io.*;
public class Main {
    static int n, arr[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0 ; i < n ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
       
        System.out.print(recur(0)); 
        return;
    }
 
    static int recur(int idx){
        if(idx==n-1) return arr[n-1];
        return (int)Math.max(arr[idx],recur(idx+1));
    }
}
  • 사고방식 오류와 해결
    • 처음엔 최댓값은 두 값을 비교해야 한다는 생각에 끌려서, 종료 조건도 마지막 두 개를 비교하는 형태로 잡았음.
    • 그런데 재귀의 종료 조건은 “마지막 연산을 어떻게 할까”가 아니라, 이 함수가 맡은 구간에서 답이 너무 당연해지는 순간으로 잡아야 함.

관련 문서