재귀함수

1. 재귀함수

🍇 재귀함수란?

자기 자신을 다시 호출하는 함수 : recursive_function()
특정한 함수가 자기자신을 포함
재귀함수는 내부적으로 스택 자료구조와 동일
⇒ 이유 : 함수를 계속 호출시 가장 마지막에 호출하기 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문
스택 자료구조를 활용해야 하는 상당수는 재귀 함수를 이용해서 간편하게 구현 가능

파이썬 예제

문자열이 무한히 출력하다가 재귀의 최대 깊이 초과시 오류가 뜸

def recursive_function(): # def는 함수를 만들 때 사용하는 예약어
	print('재귀 함수를 호출합니다.')
	recursive_function()

recursive_function()

🍇 자연수(양의 정수)

1은 자연수
자연수 n의 바로 다음 정수도 자연수이다.

🍇정렬알고리즘(병합, 퀵 정렬)

이진검색트리 활용되는 알고리즘 이다.

접근 방식

팩토리얼 구하기

음이 아닌 정수의 팩토리얼값


0! = 1
n>0 이면 n! = n x (n-1)!

5!
5x4x3x2x1= 120

int result = 0
for(int i = 5; i<0;i--){
result = result * i;

}

재귀호출(recursive call)

자신과 똑같은 구조의 메소드를 호출하는 방식
문제) 0 이상의 두정수 n, m 이 주어졌을때 n 구하시오

재귀 접근

상태 정의

재귀는 부분문제를 해결하기 위한 풀이 방법
부분문제는 각각 하나의 명확한 문제를 나타내어 하나의 답을 낼 수 있어야 한다.
답을 내는데는 입력되는 변수
이렇게 답을 결정하는 변수들을 상태(state)
하나의 상태에 대한 답을 찾는 문제
2개의 변수가 있으므로, 상태(n,m) 정의하여 표기

종료 조건

부분 문제들을 생성하여 해결해 나가다가 언젠가는 종료해야 한다.
답이 나오는 상태를 검사하여 반환할 수 있도록 종료조건
n의 0제곱을 구할때 (m=0) 답 1
0의 m제곱 구할때(n=0) 1
1의 m제곱 (n= 1) 1

(n,0)  = 1
(0,m) =1
(1,m) =1
(n,m) = n*(n,m-1)

🍇 거듭 제곱 값 구하기

import java.util.Scanner;

public class powerEx {
    private static int power(int n, int m){
        if (m == 0 ) return 1;
        if (n == 0) return 1;
        if (n==0) return 1;
        return n*power(n, m-1);
    }

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

        int result = power(n, m);
        System.out.printf("%d의 %d 거듭제곱 값 : %d", n, m, result);
    }
}

🍇 최대 공약수 구하기

import java.util.Scanner;

public class Gcd {

    private static int gCD(int x, int y){
        if(y == 0) return x;
        else return gCD(y, x%y);
     }

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

        int result = gCD(n, m);
        System.out.printf("%d의 %d 최대공약수 : %d", n, m, result);
    }
}

🍇 하노의의 탑

세 개의 기둥과 원판들이 주어졌을 때, 한 기둥에서 다른 기둥으로 모든 원판을 옮기는 문제이며, 원판들은 크기에 따라 다르며, 큰 원판 위에 작은 원판이 올라가야 한다.

핵심 : 목표는 모든 원판을 기둥 A에서 기둥 C로 옮기는 것

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12946
규칙
1. 한 번에 한 개의 원판만 이동 가능
2. 큰 원판 위에 작은 원판 올릴 수 없음
3. 어떤 기둥 위에 있는 원판은 그 기둥으로만 이동시킬 수 있음
분석

결론

원판의 개수가 1개일 경우 : 바로 기둥 A에서 기둥 C로 옮길 수 있다.
원판의 개수가 2개 이상인 경우 :

가장 작은 원판을 제외한 나머지 원판들을 기둥 A에서 기둥 B로 옮긴다.
가장 큰 원판을 기둥 A에서 기둥 C로 옮긴다.
기둥 B에 있는 원판들을 기둥 C로 옮긴다.
상태(변수)

옮기려는 원판의 개수 n
원판이 현재 위치하는 기둥값 from
원판이 이동해야 하는 기둥 to(n, from, to)
ex. 원판 n개를 기둥 1에서 기둥 3으로 옮겨라! (n, 1, 3)
- (n, from, to) ⇒ 원판 n개를 기둥 from에서 기둥 to 옮기는 과정

종료조건

원판이 1일 때 종료
(1, form, to) = [from, to] ⇒ 원판이 1개일 때는 from에서 to로 옮겨라

점화식

상태 : (n, from, to)
종료 : (1, from, to)
전이상태 : (n-1, from, to)

4 . 코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    
private List<int[]> hanoi(int n, int from, int to){
        if(n == 1) return List.of(new int[] {from, to});  //종료조건 n==1 일때 from to 이동만 시켜라
        
        //점화식 구현
        int empty = 6 - from - to;
        
        List<int[]> result = new ArrayList<>();
        result.addAll(hanoi(n-1,from,empty));
        result.addAll(hanoi(1,from,to));
        result.addAll(hanoi(n-1,empty,to));
        return result;
               
    }
    
    
    public int[][] solution(int n) {
       return hanoi(n,1,3).toArray(new int[0][]);
    }
}

다른 사람 코드

import java.util.Arrays;

class Hanoi {
    public int[][] hanoi(int n) {
        // 2차원 배열을 완성해 주세요.
        int[][] answer = {{1,3}};

    System.out.println(n);

        return answer;
    }

    // 아래는 테스트로 출력해 보기 위한 코드입니다.
    public static void main(String[] args) {
        Hanoi h = new Hanoi();
        System.out.println(Arrays.toString(h.hanoi(2)));
    }
}

🍇 하노의 원반의 개수

하노이 탑의 동작원리를 알 수 있음

// 하노이의 탑
package recurive;
import java.util.Scanner;

class Hanoi {
    //--- no개의 원반을 x번 기둥에서 y번 기둥으로 옮김 ---//
    static void move(int no, int x, int y) {
        if (no > 1)
            move(no - 1, x, 6 - x - y);

        System.out.printf("원반[%d]를 %d번 기둥에서 %d번 기둥으로 옮김\n", no, x, y);

        if (no > 1)
            move(no - 1, 6 - x - y, y);
    }

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

        System.out.println("하노이의 탑");
        System.out.print("원반의 개수 : ");
        int n = stdIn.nextInt();

        move(n, 1, 3);    // 제 1 기둥에 쌓인 n개를 제 3 기둥으로 옮김
    }
}

🍇 모음 사전

해설 : https://ksb-dev.tistory.com/273

A, E, I, O, U 만을 사용하여 5자리 이내의 문자를 만들고, 정렬하여 주어지는 문자가 몇 번째인지 반환해야 함
첫 번째 단어는 "A"이고, 두 번째 단어는 "AA"이며, 마지막 단어는 "UUUUU"

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/84512
분석

상태(word) : (word)로 시작되는 모든 단어
종료조건 : (길이가 5인 word) = word
점화식(word) =[word]+[word+'A']+[word+'E']+[word+'I']+[word+'O']+[word+'U']
종료조건 5일 때, 바로 word 반환
부분문제를 해결

private List<String> generate(String word){ 
	//종료 조건, 점화식 구현
}

// 종료조건 5일 때, 바로 word 반환
private List<String> generate(String word){
       //종료 조건 , 점화식 구현 
      List<String> wrods = new ArrayList<>();
      words.add(word);
      if(word.length() == 5) return words;

    //점화식  
  }

private List<String> generate(String word){
       //종료 조건 , 점화식 구현 
      List<String> wrods = new ArrayList<>();
      words.add(word);
      if(word.length() == 5) return words;

    //점화식   :사용될 수 있는 모든 문자를 words 붙여야 한다. 
      private static fianl char[] CHARS = "AEIOU".toCharArray();
    

  }

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    
    private static final char[] CHARS = "AEIOU".toCharArray();
    
    private List<String> generate(String word){
      
      List<String> words = new ArrayList<>();
      words.add(word);
      if(word.length() == 5) return words;

       for(char c : CHARS){
                  words.addAll(generate(word + c));
          }
       return words;
}
  
    
    
    
    public int solution(String word) {
       
        return generate("").indexOf(word);
    }
}

다른 사람 풀이

import java.util.*;
class Solution {
    List<String> list = new ArrayList<>();
    void dfs(String str, int len) {
        if(len > 5) return;
        list.add(str);
        for(int i = 0; i < 5; i++) dfs(str + "AEIOU".charAt(i), len + 1);
    }
    public int solution(String word) {
        dfs("", 0);
        return list.indexOf(word);
    }
}

class Solution {
    public int solution(String word) {
        int answer = 0, per = 3905;
        for(String s : word.split("")) answer += "AEIOU".indexOf(s) * (per /= 5) + 1;
        return answer;
    }
}

PreviousArray vs ArrayList vs LinkedList 차이 Next트리

Last updated 1 month ago