재귀용법이란?

• 함수 안에서 본인(함수)를 다시 호출하는 방식
• 재귀호출이라고도 부른다.
• 장점 : 변수 사용을 줄여줌, 가독성이 좋아짐
• 단점 : 성능이 저하된다. 왜? 재귀용법은 스택방식과 같은데, 스택 call이 반복적으로 이루어지기 때문

일반적인형태 1

def func(입력):  
    if 입력 > 어떤값:
        return func(입력-1)
    else:
        return 일정값
    
    

일반적인형태 2

def func(입력):
    if 입력 <= 어떤값:
        return 일정값
    else:
        return 결과값

---

예제1) 팩토리얼 구하기
2!, 3!, 4! ... n!을 재귀함수로 표현해 보자!

def recur_1(n):
    if n != 1:
        return n * recur_1(n-1)
    else:
        return 1

---

예제2) 숫자가 들어 있는 리스트가 주어졌을 때, 리스트의 합을 리턴하는 함수

def recur_2(lst):
    if len(lst) != 1:
        return lst[0]+recur_2(lst[1:])
    else:
        return lst[0]

더짧게 쓰면

def recur_2(lst):
    if len(lst) == 1:
        return lst[0]
    return lst[0] + sum_lst(lst[1:])

이런 방법도 있긴 있다..

---

예제3) 회문을 판별할 수 있는 함수 (회문(palindrome)은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 의미)

def palindrome(strr):
    if strr == 1:
        return True
    
    if strr[0] == strr[-1]:
        return palindrome(strr[1:-2])
    else:
        return False

재귀를 안쓰면 사실 엄청 편하게 만들 수 있다.

def recur_3(strr):
    if strr == strr[::-1]:
        return True
    return False

---

예제4)
1, 정수 n에 대해
2. n이 홀수이면 3 X n + 1 을 하고,
3. n이 짝수이면 n 을 2로 나눔
4. 이렇게 계속 진행해서 n 이 결국 1이 될 때까지 2와 3의 과정을 반복
예를 들어 n에 3을 넣으면,

3
10
5
16
8
4
2
1

과 같이 되는 함수 작성.

def func(n):
    print (n)
    if n == 1:
        return n
    
    if n % 2 == 1:
        return (func((3 * n) + 1))
    else:
        return (func(int(n / 2)))
        

---