[Data Structure] 자료구조 : 재귀(Recursion)란?

재귀 개념

 

재귀(Recursion) 개념

---

 

 

 

 

재귀(Recursion)라는 말은 들어봤을 법하다.

영어에서 재귀대명사라는 말을 들어 본 적이 있을 것이다.

myself(나 "자신"), yourslef(너 "자신")

이와 비슷한 개념이다.

재귀 함수라는 말에 적용해본다면

"나 자신을 호출하는 함수"를 의미한다.

생각을 해보자.

나 자신을 호출하는데. 계속해서 부른다면 어떻게 될까?

계속해서 반복에 빠지게 된다.

그렇기 때문에 중간에서 탈출 조건을 걸어줘야 한다.

대표적인 예시 2가지는 카운트다운과 팩토리얼 계산이 있다.

 

 

 

재귀 함수 대표 예시(파이썬, C)

---

 

 

(1) 1초 까지 카운트 다운(파이썬)

 

 

def countdown(n):
    print(n)
    if(n<=1):
        return
    else:
        return countdown(n-1)
    
# countdown(3)
# 3
# 2
# 1

 

---

 

(2) 팩토리얼

 

ㄴ1) 재귀 (파이썬)

 

< 확인 체크 >

 

0! = 1

1! = 1

 

def factorial(n): 
    if(n==0): 
        return 1 
    else: 
        return n*factorial(n-1) 
     
# factorial(5)
# 120

---

ㄴ2) 반복문 (파이썬)

 

 

def factorial(n):
    result = 1
    
    if n==0:
        return 1
    while n > 0:
        result *= n
        n -= 1
    return result
 
# factorial(5)
# 120

---

 

 

ㄴ3) 재귀 (C)

 

#include <stdio.h>
#include <stdlib.h>
 
int factorial(int);
 
int main(){
    int result;
 
    result = factorial(5);
    printf("5의 팩토리얼 값은? %d", result); //result = 120
}
 
int factorial(int n){
 
    if(n==0){
        return 1;
    }else{
        return n*factorial(n-1);
    }
}
 

 

 

---

재귀 자체를 따로 보는 것이 아니라 왜 나왔는지 반복문을 생각해보면 빠르게 학습이 가능하다.

 

반복문을 이용하는 것을 조금 더 효율적으로 이용하기 위해 나온 개념이구나 라는 정도면 충분한 것 같다.

(마치 덧셈을 하다가, 곱셈의 효율성을 알아간다는 느낌으로)

그렇기에 학습 순서는 반복문 - > 재귀가 가장 좋다고 생각한다.

언뜻 보기에 깔끔하고, 있어보는 재귀이지만 재귀 호출로 인한 알고리즘 구현은 횟수 제한이 있어 while문으로 처리해야 하는 경우가 있기에 2가지 모두 알고 있는 걸 추천한다.