모각코 5일차 결과 (2. 10)

인프런에서 권오흠 교수님의 알고리즘 강좌를 듣고 필기한 내용이다.

수강한 파트는 Recursion이다.

Recursion이 무한 루프에 빠지지 않으려면..

1. Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.

2. Recursvie case : recursion을 반복하다보면 결국 base case로 수렴해야 한다.

ex)

public class Code02{

    public static void main(String[] args){

        int n = 4;

        func(n);

    }

}

public static void func(int  k){

    if (k <= 0){ <- Base case

        return;

    }else{ <- Recursvie case

        System.out.println("Hello...");

        func(k-1);

    }

}

---------------------------------------------------------------------------------------------------------------------

Recursvie Thinking

수학 함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있음

1. 문자열의 길이 계산, 문자열의 프린트, 문자열을 뒤집어 프린트

2. 2진수로 변환하여 출력

3. 배열의 합 구하기

4. 데이터파일로부터 n개의 정수 읽어오기

Recursion VS Iteration

- 모든 Recursive 함수는 반복문(iteration)으로 변경 가능

- 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능

- Recursive function은 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 한다.

  그러나, 함수 호출에 따른 오버헤드가 존재한다. (매개 변수 전달, 스택 프레임 생성 등)

---------------------------------------------------------------------------------------------------------------------

Designing Recursion

Recursion Algorithm 설계

- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함

- 모든 case는 결국 base case로 수렴해야 함

암시적(implicit) 매개변수를 -> 명시적(explicit) 매개변수로 바꾸어라

1, 순차탐색

2. 최대값 찾기

3. Binary Search