Recursion 1-2

2021.10.14 - [알고리즘/재귀] - Recursion 1-1 ( 순환, 재귀)

Recursion 1-1 ( 순환, 재귀)

# 모든 코드는 C++ 로 작성되었습니다~!

 

Recursion 1-2 

기존에 반복문으로 구현했던거를 다시 recursive하게 구현하려고 하니 머리가 아프다 아무래도 적응이 필요할것 같다. ㅠ

 

조금 더 도움이 되기 위해서 Recursion을 설계 방법(요령)을 한 번 알아보자!!

일단 기본적으로 지켜야 될 규칙은 저번에 말했던 거와 같이 2가지이다.

• Base case 는 적어도 1개 이상 존재 (종료조건)
• Recursive step은 결국  bass case로 수렴 

이 두가지를 지키면서 한 가지 추가해야할 개념은 임시적 매개변수를 명시적 매개변수로 바꿔야 한다는 것이다!!

음 ... 처음에는 무슨 이야기 인가 갸우뚱했다 .

반복문 같은경우에는 인자가 적은게 아무래도 좋지만 Recursive 함수를 만들 때는 매개변수들을 눈에 보이게! 표시하는게 좋다는 것이다 . 

 

#순차탐색 : 배열안에 특정한 값을 찾는방법 (배열안의 원소가 정렬 안 된 상태 ) 

#이진탐색 : 배열안에 특정한 값을 찾는방법 (배열안의 원소가 정렬 된 상태)

 

순차탐색으로 예를 들어보자면 반복문의 경우에는

#include <iostream>
using namespace std;

int Seach(int arr[], int size , int target){
    for (int i =0; i< size; i++){
        if(arr[i] == target){
            return i; // 원하는 값의 index return
        } // if 
    } //for
    return -1; // 찾는 값이 없는경우
}

int main(){
    int a[5] = {1,2,3,4,10}; // 원소가 5개인 배열 생성
    int size = 5;   // 배열의 사이즈 
    int target = 10;  // 찾고자 하는 숫자
    cout << "index of target : " << Seach(a,size,target) << endl;
    return 0;
}

이와 같이 반복문으로도 구현이 가능하다 한 번 출력값을 확인을 해보자

순차탐색 (반복문)

출력값도 잘 나왔다 ! 여기서 우리는 Serach 함수를 보면 자연스럽게 시작점은 index 0 이라고  암묵적으로 생각하고있다.  반복문으로 짠 코드도 훌륭하지만 우리가 여기서 이 코드를 Recursive하게 짜기 위해서는 이런 암묵적인 시작점을 일반화 시켜줘야한다!!(명시적!)

 

다음으로 시작점을 명시하여 recursive하게 코드를 구현해보면

#include <iostream>

using namespace std;

int Seach(int arr[], int begin ,int end ,int target){
    if(begin > end){return -1;}  // 찾는 값이 없는경우
    else if(target == arr[begin]){return begin;} 
    else{
        return Seach(arr, begin+1 , end , target); // 시작점 1칸이동!
    }
}

int main(){
    int arr[5]  = {5,3,6,1,2}; // 1은 index 3번
    int begin = 2;
    int end = 4;
    int target = 1;
    cout << "index of target :"  << Seach(arr,begin,end,target)<<endl;
    return 0;
}

이렇게 Recursive하게 구현이 가능하다 !! 출력값을 확인해보면

순차탐색 (재귀)

출력값도 잘 나왔다 ! 이렇게 시작점을 명시화 시켜주면서 함수를 다시 호출할때 시작점을 한 칸 이동하는것으로 구현이 가능하다 이렇게 명시화를 한다면 end 부터 begin 까지 반대로 찾는것도 가능하며 또한 중간이 middle 에서 탐색을 가능하게 할 수 있다!  나머지 두 개를 스스로 한번 구현해보장!

 

그렇다면 최대값 찾기를 recursive하게 구현해보자 물론 for문을 사용하면 쉽게 구현할 수 있지만 우리의 재귀와 친숙해지기 위해 자주 사용해보자!

 

-최대값 찾기

#include <iostream>

using namespace std;
int max_v(int arr[], int begin , int target){
    int max = arr[0];
    for(int i=0; i<begin; i++){
        if(max < arr[begin] ){
            max = arr[begin];
        }
    }
    if(max <target){max = target;}
    return max ;
}

int Max_value(int arr[], int begin , int end ){
    if(begin == end){return arr[begin]; }
    return max_v(arr,begin, Max_value(arr, begin+1 , end));
}



int main(){
    int arr[5] = {2,3,5,20,8};
    int begin = 0;
    int end = 5; 
    cout << "Max_Value : " << Max_value(arr,begin, end) << endl;

    return 0;
}

max 함수까지 새로 구현해 봤다 !! 어렵지만 할만하다!! 출력값을 확인해보자

최대값 (재귀적)

반복문으로 구현하다면 정말 쉬운 코드이지만 recursive하게 구현하려니 쉽지가 않다 머리가 너무 띵하다 

말로 하기는 힘들지만 하나 요령이 생겼다면 

결국 최대값은 (한 부분에서 최대값 ) 그리고 (나머지 부분의 최대값) 중 더 높은 숫자가 최대값이라는거다

정말 당연한 소리이지만 이 부분에 대해서 확실하게 받아들일 수 있다면 recursive하게 함수를 구현하는것은 더 수월해 질 것이다!! 아님말고~