재귀함수 -> 꼬리물기 재귀함수 -> 반복문

재귀함수를 꼬리 재귀 함수로 변환하고, 그 다음 반복문으로 변환하는 것은 재귀 호출을 명시적인 반복 구조로 바꾸는 과정입니다.

꼬리 재귀는 함수의 마지막 작업이 자기 자신을 호출하는 형태로, 이론적으로는 반복문으로 쉽게 변환할 수 있습니다.

꼬리 재귀를 반복문으로 바꾸는 이유는 스택오버플로우 때문입니다.

그렇게 때문에 꼬리재귀함수 와 반복문간의 코드 변환은 자유자재로 할수 있어야 합니다.

재귀함수 문제 중에서 다른 문제로는 다음과 같은 것들이 있습니다.

https://www.youtube.com/watch?v=h80tLv0fn88&list=PLBNdLLaRx_rKOFzA3txlG5rf9ZaVUuvmv&index=2

10분정도 후 부터 tail recursion 보시면 됩니다.

 

1. 피보나치 수열

피보나치 수열은 각 숫자가 두 이전 숫자의 합인 수열입니다. 재귀적으로 구현할 수 있으며, 메모이제이션을 사용하여 성능을 개선할 수 있습니다.

2. 최대공약수(GCD) 계산

유클리드 호제법을 사용하여 두 수의 최대공약수를 재귀적으로 계산할 수 있습니다. 이 방법은 두 수를 나누고 나머지를 계속 계산하여 나머지가 0이 될 때의 나누는 수가 최대공약수입니다.

위처럼 10과 15가 있을 때 계속적으로 대입하고 나누다보면 y 가 5일 때 r 이 0이 되기때문에  최대공약수는 5 가 됩니다.

:꼬리재귀함수

const gcd=(a,b)=>{
    if(b == 0) return a;
    return gcd(b,a%b);
};
console.log(gcd(18,15));

:반복문

let a=18, b=15;
while (b) {
    [a, b] = [b, a % b];
}
console.log(a);

3. 문자열 뒤집기

문자열을 재귀적으로 뒤집는 문제입니다. 문자열의 첫 번째 문자와 나머지 문자열을 분리하여 재귀적으로 뒤집은 후, 첫 번째 문자를 뒤에 붙이는 방식으로 구현할 수 있습니다.

:꼬리재귀함수

const arrT='hello';
const arr = [...arrT];
const str=(num,acc=[])=>{
	if(num<0) return acc;
    acc.push(arr[num]);
    return str(num-1, acc);
};
str(arr.length-1);

:반복문

const arrT='hello';
const arr=[...arrT];
let num=arr.length-1;
let acc=[];
while(num>=0){
	acc.push(arr[num]);
    num=num-1;
}
console.log(acc);

4. 이진수 변환

정수를 이진수로 변환하는 문제로, 정수를 2로 나누고 나머지를 기록하면서 재귀적으로 처리할 수 있습니다.

:꼬리재귀함수

const deci=(num,acc='')=>{
	if(num == 0) return acc;
    	return deci(Math.floor(num/2), (num%2).toString() + acc);
};

deci(10);

:반복문

let num=10, acc='';
while(num>0) {
    num = Math.floor(num/2);
    acc = (num%2).toString() + acc;
}
console.log(acc);

5. 조합 생성

주어진 집합에서 가능한 모든 조합을 생성하는 문제로, 재귀적으로 부분 집합을 선택하거나 선택하지 않는 방식으로 구현할 수 있습니다.

6. 하노이 탑

하노이 탑 문제는 세 개의 기둥과 여러 개의 원반을 사용하여, 모든 원반을 한 기둥에서 다른 기둥으로 옮기는 문제입니다. 재귀적으로 원반을 이동하는 과정을 구현할 수 있습니다.

const hanoi=(n,from,to,via)=>{
    if(n==0) return;
    
    hanoi(n-1,from,via,to);
    
    console.log(` ${from} -> ${to} move `);
    hanoi(n-1,via,to,from);
};
hanoi(3,1,3,2);

7. 팩토리얼 계산

팩토리얼은 주어진 수의 모든 양의 정수의 곱을 계산하는 문제로, 재귀적으로 구현할 수 있습니다. 예를 들어, 𝑛!=𝑛×(𝑛−1)!n!=n×(n−1)!로 표현할 수 있습니다.

8. 프로그래머스  day14  1로 만들기

문제 설명

정수가 있을 때, 짝수라면 반으로 나누고, 홀수라면 1을 뺀 뒤 반으로 나누면, 마지막엔 1이 됩니다. 예를 들어 10이 있다면 다음과 같은 과정으로 1이 됩니다.

10 / 2 = 5

(5 - 1) / 2 = 2

2 / 2 = 1

위와 같이 3번의 나누기 연산으로 1이 되었습니다.

정수들이 담긴 리스트 num_list가 주어질 때, num_list의 모든 원소를 1로 만들기 위해서 필요한 나누기 연산의 횟수를 return하도록 solution 함수를 완성해주세요.

제한사항

3 ≤ num_list의 길이 ≤ 15

1 ≤ num_list의 원소 ≤ 30

입출력 예

num_list    result

[12, 4, 15, 1, 14]  11

입출력 예 설명

입출력 예 #1

12는 3번, 4는 2번, 15는 3번, 1은 0번, 14는 3번의 연산이 필요하기 때문에 총 11번의 연산이 필요합니다.

:꼬리재귀함수

function solution(num_list) {

    const res=[];
    const recur=(n,v)=>{
        if(v == 1) return n;
        if( v%2 == 0 ) v = v/2;
        else v = (v-1)/2;
        
        return recur(n+1, v);
    };
    
    num_list.map(v=>{
        res.push(recur(0,v));
    });
    return res.reduce((v,acc)=>acc+=v, 0);
    
}

:반복문

function solution(num_list) {
    let h=0;
    num_list.map(v=>{
        let n=0;
        while(v>1) {
            if( v%2 == 0 ) v = v/2;
            else v = (v-1)/2;
            n++;
        }
        h+=n;
    });
    
    return h;
}

9. 프로그래머스  day15  문자열이 몇 번 등장하는지 세기

문제 설명
문자열 myString과 pat이 주어집니다. myString에서 pat이 등장하는 횟수를 return 하는 solution 함수를 완성해 주세요.

제한사항
1 ≤ myString ≤ 1000
1 ≤ pat ≤ 10
입출력 예
myString pat result
"banana" "ana" 2
"aaaa" "aa" 3
입출력 예 설명
입출력 예 #1

"banana"에서 1 ~ 3번 인덱스에서 한 번, 3 ~ 5번 인덱스에서 또 한 번 "ana"가 등장해서 총 두 번 등장합니다. 따라서 2를 return 합니다.
입출력 예 #2

"aaaa"에서 0 ~ 2번 인덱스에서 한 번, 1 ~ 3번 인덱스에서 한 번, 2 ~ 4번 인덱스에서 한 번 "aa"가 등장해서 총 세 번 등장합니다. 따라서 3을 return 합니다.

:꼬리재귀함수

function solution(myString, pat) {
    
    const recur=(start, count=0)=>{
        const found = myString.indexOf(pat, start);
        if(found == -1) return count;
        
        return recur(found+1, count+1);
    };
    return recur(0);
}

:반복문

function solution(myString, pat) {
    let start=0, count=0;
    while(1) {
        const found = myString.indexOf(pat, start);
        if( found == -1) break;
        start = found + 1;
        count = count + 1;
    }
    return count;
    
}