TIL (2022/01/20)

(1) 재귀함수 with no return

void helloWorld(int number){

    // 종료조건이 필요함
    if(number==0){
        return;
    }
    
    helloWorld(number-1); 
    cout<<"HelloWorld"<<endl;
}

N = 1,2,..,N;
if n==0 return;
p(n-1) <- 여기서 멈추고 재귀
cout<<n<<" ";

만약 n = 4 :
p(4) -> p(3) -> p(2) -> p(1) 다음은 종료조건이기에 여기서 멈춤

p(1)로 다시 돌아가서 1
p(2)로 다시 돌아가서 2
p(3)로 다시 돌아가서 3
p(4)로 다시 돌아가서 4

--

N = N,N-1,...,1
if n==0 return;
cout<<n<<" ";
p(n-1)

만약 n = 4 :
4 -> 3 p(3) -> 2 p(2) -> 1 p(1) -> 종료조건


재귀함수를 이용한 별출력
n=5라면 
void stars(int n){
    if (n==0) return ;
    stars(n-1); // 여기서 4,3,2,1이 되고 그게 종료 조건을 만나면 거꾸로 1부터 올라가는 것
    for(int i=0;i<n;i++){
        cout<<"*";
    }
    cout<<endl;
}

output
*
**
***
****
*****

5 4 3 2 1 1 2 3 4 5 재귀함수로 구현

void upanddown(int number){
    if(number==0) return;
    cout<<number<<" ";
    upanddown(number-1);
    cout<<number<<" ";
}

(2) 재귀함수 with return

1부터 입력값까지의 합
예를 들어 n = 2
int addition(int number){

	// 종료조건
    if (number==0) return 0;
    // addition(1)+2 -> addition(0)+1 = 3;
    return addition(number-1)+number;
    
}

숫자의 각 자리 합은 앞의 자리들 + 마지막 자리의 형태
F(n) = F(n을 10으로 나눈 몫) + (n을 10으로 나눈 나머지)

int square(int number){
    if (number<10){
        return number*number;
    }

    int digit = (number%10);
    return square(number/10)+digit*digit;
}
-> F(1527) = F(152)+7*7;
F(n) = F(n/10)+(n%10)%(n%10);

number에서 시작해서 1이 되기 위해 필요한 횟수를 반환

int division(int number){
    // 1에서 시작하면 바로 끝나니 0회
    if(number==1) return 0;
    // 나누고 +1
    if(number%2==0) return division(number/2)+1;
    else return division(number/3)+1;
}

피보나치 수열 만들기
int fibo(int number){
    if(number<=2) return 1;
    return fibo(number-1)+fibo(number-2);
}

number가 3일때, 3번째 위치의 값
1 1 2 
fibo(2)+fibo(1) = 2

number가 4일때, 4번째 위치의 값
1 1 2 3 
fibo(3)+fibo(2) = 3
fibo(3) = fibo(2)+fibo(1) =2
fibo(1) = 1

(3) factorial

int factorial(int number){
    if(number==0) return 1;
    return factorial(number-1)*number;
}

(4) 자릿수 다 더하기

int print(int number){
    if(number<10) return number;
    return print(number/10)+print(number%10);
}

(5) 최댓값 구하기

int max_Val(int n){
    if(n==0){
        return arr[n];
    }
    return max(max_Val(n-1),arr[n]);
}

(6) 3n+1 수열 구하기

n에서 시작하여 n이 짝수면 2로 나누고
n이 홀수면 3을 곱하고 1을 더하는 것

몇 번을 반복해야 1이 되는가?

int count(int n){
    if(n==1) return 0;
    // 1을 더하는 이유 = 트라이 횟수
    if(n%2==0) return count(n/2)+1;
    else return count(3*n+1)+1;
}