재귀
재귀란 ?
재귀란 원래의 자리로 되돌아가거나 되돌아옴. - 네이버 국어사전 -
네이버 국어사전에는 재귀가 원래의 자리로 되돌아가거나 되돌아 온다고 적혀있다.
그렇다면 알고리즘에서의 재귀 또한 비슷할까 ?
(위의 스폰지밥 밈은 내가 재귀를 배우면서 가장 재귀 다운(?) 밈이라 생각해서 올려봤다.)
재귀에 대한 간단한 예시
Udemy에서 자바스크립트로 배우는 알고리즘 강의를 구매해 배우고 있다.
Colt Steele 선생님의 재귀 비유를 잠시 빌리려 한다.
선생님 허락해 주실 거죠 ...?
옛날 한 마법사과 용이 있었다.
마법사는 마법 학교에서 하나의 과제를 받았는데 이는 [2222, 5554, 8264, 1024]의 배열 중 홀수를 찾는 것이였다.
용은 짝수와 홀수를 구분하는 능력이 있다. 그래서 마법사는 용을 찾아가 배열을 보여주며 홀수를 모두 찾아주라고 부탁했다.
🐲: 나는 배열의 첫 번째 숫자만 홀수인지 알려준다 ! 🔥🔥🔥
🧙: 그래 그럼 배열의 첫 번째 숫자만 홀수인지 알려줘 !
🐲: [2222, 5554, 8264, 1024]의 첫 번째 수인 2222는 홀수가 아니다 !
🧙: 도루마무(?) [5554, 8264, 1024] 배열의 첫 번째 숫자가 홀수인지 알려줘 !
🐲: [5554, 8264, 1024]의 첫 번째 수인 5554 홀수가 아니다 !
🐲: 어...?
위의 대화 내용에서 마술사는 꼼수(?)를 쓰는데 이는 기존 배열의 맨 앞 부분이 홀수인지 짝수인지를 확인하고
지운 뒤 다시 용에게 물어보는 행동을 마지막 숫자까지 반복한다.
(용도 마법 앞에선 한낯 도마뱀에 불과한가...?)
재귀를 코드로 살펴보자
자 그럼 간단한 설명을 마쳤으니 본격적인 코드로 재귀를 알아보겠다.
function recursion(num){
if(num === 1) return 1;
return num = num + recursion(num-1)
}
recursion(3)위의 코드에서 신기한 걸 볼 수 있는데 바로 recursion 함수 안에 recursion를 실행 시킨다는 것이다.
🤨: 아니 자기 자신을 어떻게 실행시켜 ?!
그렇다 자기 자신을 어떻게 실행시킬까라는 의문이 생기고 코딩 초보자가 저 코드를 처음보고 해석하기에는
조금 어려울 것이다. 나도 어제 보고 이게 뭔가 싶었다.
코드를 조금 더 풀어서 설명해보자
- 처음 recusion의 num은 3이 들어가고 num은 1이 아니기에 num = num + recursion(num-1)을 리턴한다.
- 리턴 값 num = num + recursion(2)은 안 쪽에 recursion 함수가 실행되어야 리턴 값을 받아 올 수 있다.
- 그렇다면 다시 recursion에 num은 2가 들어가고 num이 1이 아니기에 다시 num = num + recursion(1)을 실행한다.
- 그럼 또 다시 recursion에 num은 1이 들어가고 if문에서 return 은 1로 반환된다.
- 마지막으로 지금까지의 계산을 모두 되돌아가서 num값을 모두 더한 값을 반환하게 되는 것이다.
글로 설명하자면 이렇다. 그런데 사실 글로 봐도 뭐가 뭐라는지 잘 모르겠다.
코드에 조금 더 자세하게 설명을 붙여 보겠다.
// 자세한 해설
function recursion(num){
if(num === 1) return 1;
return num = num + recursion(num-1)
}
recursion(3) // 6
recursion(3) // 3을 넣으면 num = num + recursion(2)을 리턴
num = num + recursion(2) // num + recursion(2)을 먼저 리턴 해야함
num = num + recursion(1) // num + recursion(1)을 먼저 리턴 해야함
1 // num이 1이니 1을 리턴
num = 2 + recursion(1) // 다시 되돌아가 recursion(1)은 1을 반환한다.
//recursion(2)은 2 + 1 즉 3이 된다.
num = 3 + recursion(2) // recursion(3)은 3 + 3 즉 6이 된다.
나의 최선을 다한 설명이였다...
재귀 VS 반복문
사실 위의 코드는 우리가 흔히 사용하는 while/for문으로 충분히 만들 수 있다.
function forRecursion(num){
let sum = 0;
for(let i = num; i > 1; i--){
sum += num
}
return sum
}
forRecursion(3); // 6아니 그렇다면 반복문을 활용하면 되는데 굳이 함수 안에 함수를 넣는 이유가 무엇인가 ?
그걸 알아보기 위해 우리는 재귀와 반복문의 차이를 알아 볼 필요가 있다.
재귀와 반복문의 장단점
-
재귀
장점: 간략한 코드로 인한 가독성 증가와 코드의 길이가 줄어듬
단점: 반복문보다 느린 실행속도, stack overflow의 위험성 -
반복문
장점: 재귀보다 빠른 실행 속도
단점: 재귀보다 상대적으로 복잡한 코드와 많은 코드
😯 : 아니 비교했을 때 반복문이 더 좋은데 ...?
라고 생각할 수 있다.
반복문과 비교를 했을 때 재귀는 코드의 가독성과 길이가 줄어든다는 장점 외에 반복문 보다는 특별히 뛰어난 점이 없다.
그럼에도 불구하고 재귀 함수를 배우고 사용하는 이유는 무엇일까 ?
재귀의 사용 이유와 위험성
1. 재귀를 사용하기 좋은 알고리즘이 존재한다.
대표적인 예시가 하노이탑과 피보나치 수열이다.
이런 예시들과 같은 재귀적 알고리즘을 풀 때는 재귀를 사용하는 것이 좀 더 합리적이라고 볼 수 있다.
2. 변수를 줄 일 수 있다.
위에서 설명한 재귀의 변수는 num이라는 매개변수 하나가 전부인 반면
for문은 함수 내부에 sum이라는 변수와 for문에 i를 생성하여 그것을 return 시킨다.
변수를 줄어 든다면 그만큼 사이드 이펙트를 줄일 수 있다는 것이다.
3. 높은 가독성과 짧아지는 코드
장점에서 말했듯이 반복문과 차별되는 점이다.
단순 저렇게 비교를 했을 때 성능이 안 좋다는 재귀를 왜 사용 해야하는지 이해가 안갈 수 있다.
요즘 H/W의 성능은 대체로 다 좋은 편이다. S/W에서 성능을 최고로 끌어 올릴 필요가 없다.
그렇다면 협업을 중시하고 가독성과 간략한 코드를 원하는 현대 개발 문화에 조금 더 어울린다 할 수 있다.
하지만 재귀를 사용 할 때 가장 중요한 것이 있다.
바로 Stack Overflow 현상이다.
(우리가 모르는거 물어보는 성역과 같은 이름이다.)
재귀는 하나의 함수가 원하는 값을 얻을 때 까지 계속해서 함수(자기 자신)을 선언하게 되는데
이렇게 함수가 계속 선언되면 스택(Stack) 메모리에 자기 자신을 계속 쌓게 된다.
만약 이 함수가 멈추지 않는 시속 300Km의 람보르기니와 같이 계속해서 자신을 메모리에 쌓게 된다면 ?
Stack Overflow가 발생해 메모리 제한이 있는 프로그램은 비정상적으로 종료하게 된다.
반면의 반복문은 무한 반복하게 되면 종료되지 않고 계속해서 실행된다.
(예전에 웹에서 무한 루프 걸린 기억이...)
function recursion(num){
if(num === 1) return 1;
return num = num + recursion(num-1)
}
recursion(3) // 6그래서 위의 재귀 코드를 보면 if(num === 1) return 1 이라는 조건문이 중단점의 역활을 하는 것이다.
만약 이 중단점이 없거나 조건을 잘못 설정한다면 Stack Overflow 현상을 맞닥 뜨리게 될 것이다.
오늘의 느낀점✍
재귀를 공부하면서 가장 먼서 생각이 났던 게 바로 인셉션이였다.
자신의 꿈 속의 자신의 꿈 속의 자신의 꿈...과 같은...
재귀를 공부하면서 현업에서 꽤나 자주 쓰일 거 같고 함수형 프로그래밍을 할 때 중요한 알고리즘 중 하나라고 생각이든다.
프로그래머스 문제를 풀 때 하노이탑와 피보나치 수열에 관한 문제가 있었는데
재귀를 학습하기 전에는 반복문만 생각하며 머리를 쥐어 짜낸 기억이 있다.
재귀의 내용을 다시 한번 이해하고 문제를 다른 방법으로 접근하고 풀어 볼 생각이다.
