[코드스테이츠] 05_10_TIL : 알고리즘 / 자료구조 _ 재귀함수 이론

Today I Lean

알고리즘 / 자료구조 _ 재귀함수 이론

 

 

 

 

 

학습목표 및 개념정리

#  재귀 함수

- 재귀적으로 사고하는 법을 터득한다.

- 문제를 잘게 쪼개 사고할 수 있다.

- 메서드 자신의 재귀적 호출과, 탈출 조건을 설정할 수 있다.

- JSON구조에 재귀함수를 활용할 수 있다.

 

 

 

 

배운 것

# 재귀 함수

1. 재귀 란?

 : 원래의 자리로 되 돌아 가거나 되돌아 오는 것

 → 자기 자신을 호출하는 함수

재귀 함수
장점	단점	사용 조건
- 불필요한 반복문을 사용하지 않음 - 간결한 코드 - 수정 용이 - 간단한 변수 사용 가능	- 직관적인 코드 흐름 파악이 어려움 - 메서드 반복 호출시 그 값을 모두 stack 메모리에 저장, 메모리가 많이 사용됨 - 메서드를 호출/종료 이후 복귀를 위한 컨텍스트 스위칭 비용 발생	- 문제의 크기를 작은 단위로 쪼개야 함 - 재귀 호출이 종료되는 시점이 존재필요

 

2. 반복문 vs 재귀

- 재귀가 적합한 상황
 : 주어진 문제를 비슷한 구조의 더 작은 문제로 나눌 수 있는 경우

 : 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우

 : 변수 사용을 줄여 mutable state(변경가능한 상태)를 제거하여 프로그램 오류가 발생할 수 있는 가능성을 줄이는 경우

 

 

3. 재귀적 사고

- 재귀 함수의 입력값, 출력값 정의하기

 : 문제를 가장 단순하게 줄이기

 → 함수명 : [입력값]  > 출력값

 

- 문제를 쪼개고 경우의 수 나누기

 : 입력값이나 문제의 순서, 크기를 기준으로 봄

 : 문제를 푸는 방식이 순서나 크기에 관계없이 모두 같다면 문제를 제대로 구분한 것

 

- 단순한 문제 해결하기

 : 가장 해결하기 쉬운 문제부터 해결하는것이 재귀의 기초(base case)

 : 이 재귀의 기초는 탈출조건(재귀 호출이 멈추는 조건)을 구성함

 → 함수 arrSum을 더 이상 쪼갤 수 없는 경우는 빈배열일 경우임, 이때 arrSum(new int[]{})의 리턴값은 0

 → 재귀 탈출조건은 return 0;

- 복잡한 문제 해결하기
 : 배열을 head(가장 앞)와 tail(가장 끝)로 구분

 

 

 

4. 구구단 만들기

public class Main {
    public static void main(String[] args) {
        Gugudan gugudan = new Gugudan();

        System.out.println("GugudanFor");
        gugudan.GugudanFor(2);

        System.out.println("GugudanRecursion");
        gugudan.GugudanRecursion(3,3);

    }
}

public class Gugudan {
	// 반복문 사용
    public void GugudanFor(int level) {
        for (int count = 1; count < 10; count++) {
            System.out.printf("%d x %d = %d\n", level, count, level * count);
        }
    }
	
    // 재귀 사용
    public void GugudanRecursion(int level, int count) {
        if(count >9) {
            return;
        }
        // 재귀함수 탈출문 : 계속 +1되던 count값이 9보다 커질 경우 종료

        System.out.printf("%d x %d = %d\n", level, count, level * count);
        // 1. 입력받은 level과 count의 값을 곱하고 곱한 값을 리턴
        // 3. 2번에서 입력받은 수를 다시 곱하고 곱한 값을 리턴
        GugudanRecursion(level, ++count);
        // 2. level은 입력받은 수 그대로, count는 +1
        // 4. 위 1~3번까지의 과정을 if문의 조건까지 반복
    }
}

// 출력 결과
GugudanFor
2 x 1 = 2
2 x 2 = 4
2 x 3 = 6
2 x 4 = 8
2 x 5 = 10
2 x 6 = 12
2 x 7 = 14
2 x 8 = 16
2 x 9 = 18
GugudanRecursion
3 x 3 = 9
3 x 4 = 12
3 x 5 = 15
3 x 6 = 18
3 x 7 = 21
3 x 8 = 24
3 x 9 = 27

 

 

 

5. 팩토리얼

import Recursion.*;

public class Main {

        Factorial factorial = new Factorial();
        
        System.out.println("FactorialFor");
//        factorial.FactorialFor(5);
        // Factorial 클래스가 void가 없다는 것을 까먹어서 반환타입 지정을 안했더니 결과값이 안나옴
        // int로 반환타입 지정하고, sout 해서 출력
        int resultFor = factorial.FactorialFor(5);
        System.out.println(resultFor);

        System.out.println("FactorialRecursive");
//        factorial.FactorialRecursive(6);
        int resultRecursive = factorial.FactorialRecursive(6);
        System.out.println(resultRecursive);
    }
}

package Recursion;

public class Factorial {

    // 반복문 사용
    public int FactorialFor(int number) {
        int result = 1;
        for (int count = number; count > 0; count--) {
            result = result * count;
        }
        return result;
    }

    // 재귀 사용
    public int FactorialRecursive(int number) {
        if(number <= 1) {
            return 1;
        }
        return number * FactorialRecursive(number - 1);
    }
    
    // 재귀 사용시 중간 계산 결과를 보고 싶을 때
    public int FactorialRecursive(int number) {
        if(number <= 1) {
            System.out.printf("FactorialRecursive(%d) = 1\n", number);
            return 1;
        }
//        return number * FactorialRecursive(number - 1);
		// 인트타입으로 리절트를 정의해 주고
        int result = number * FactorialRecursive(number - 1);
        System.out.printf("FactorialRecursive(%d) = %d%n", number, result);	//리절트 결과값 반환
        return result;
    }
}

// 출력 결과 
FactorialFor
120

FactorialRecursive
720

FactorialRecursive
FactorialRecursive(1) = 1
FactorialRecursive(2) = 2
FactorialRecursive(3) = 6
FactorialRecursive(4) = 24
FactorialRecursive(5) = 120
FactorialRecursive(6) = 720
720

 

 

 

 

*****

코플릿 12번 문제 해석

 

 

 

 

Tomorrow Chapter

# 재귀함수 과제

 

 

 

---

 

 

↓ 이전 글 ↓

2023.05.09 - [분류 전체보기] - 스레드와 JVM

 

 

↓ 코트스테이츠 부트캠프 관련 글 한번에 보기 ↓

'IT/코드스테이츠 부트캠프' 카테고리의 글 목록