[Python] - 재귀 함수 : 값을 반환. return value. factorial. 각 자리 숫자합, 점화식 및 수열

1. 값을 반환하는 재귀함수 - factorial

- 1부터 n까지의 곱을 반환하는 factorial(n)을 재귀함수로 구현하기

- factorial(n)은 n * (n-1) * (n-2) *... * 3 * 2 * 1이다.

- factorial(n-1)은 (n-1) * (n-2) *... * 3 * 2 * 1이다.

- factorial(n) = factorial(n-1) * n이다.

 

def factorial(n):
    return factorial(n-1)*n

 

- 하지만 재귀함수는 종료조건이 없으면 계속 호출을 반복한다.

- 값을 반환하는 재귀함수의 종료조건은 계산 없이도 바로 결과를 알 수 있는 경우로 설정한다.

- factorial 함수에서 1! 은 1이라고 당연히 알고 있기 때문에 이를 종료조건으로 설정한다.

 

def factorial(n):
    if n==1: return 1
    return factorial(n-1)*n

 

- 따라서 5!, 즉 factorial(5)는 120이라는 것을 알 수 있다.

def factorial(n):
    if n==1: return 1
    return factorial(n-1)*n

print(factorial(5))

 

결과

120

 

factorial(5)의 흐름

 

● 값을 반환하는 재귀함수의 Key Point

1. 동일한 상황이 반복되는 것을 재귀적으로 찾기

2. 당연한 종료조건을 정의

---

Q) 1부터 특정 수까지의 합

- 정수 n을 입력

- 1부터 n까지의 합을 구하시오

 

def total_sum(n):
    if n==1: return 1
    return total_sum(n-1)+n

n=int(input())
print(total_sum(n))

 

결과

>> 100
5050

 

---

2. 각 자리의 숫자 합

- 숫자 12345의 각 자리 숫자의 합은 1+2+3+4+5=15이다.

- 이는 1234의 각 자리 숫자의 합과 5를 더한 값과 같다.

- 각 자리 숫자의 합을 구하는 함수를 each_sum이라 하자.

- each_sum(12345)=each_sum(1234)+5

- 따라서 이를 일반화하면 each_sum(n) = each_sum(n//10) + (n%10)

- 즉, n을 10으로 나눈 몫의 각 자리의 합과 n을 10으로 나눈 나머지를 더한 것과 같다.

- 종료조건은 n이 한 자리인 경우 n을 반환한다. ex) each_sum(5) = 5

 

def each_sum(n):
    if n<10:
        return n

    return each_sum(n//10)+(n%10)

print(each_sum(12345))

 

결과

15

 

---

Q) 각 자리의 제곱 합

- 정수 n을 입력

- n의 각 자리의 숫자의 제곱 합을 출력하라

 

def each_square_sum(n):
    if n<10:
        return n**2
    return each_square_sum(n//10)+(n%10)**2

n=int(input())
print(each_square_sum(n))

 

결과

>> 12345
55

- 1*1 + 2*2 + 3*3 + 4*4 + 5*5 = 1+4+9+16+25 = 55

 

---

Q) 1이 되기까지 동작 횟수

- 정수 n을 입력

- n이 짝수이면 2로 나누고, 홀수이면 3으로 나눠 몫을 구한다.

- 몫이 1이 되면 그전까지의 작업 횟수를 출력하라.

 

def get_count(n):
    if n==1: return 0
    
    if n%2==0: return get_count(n//2)+1
    else: return get_count(n//3)+1

n=int(input())
print(get_count(n))

 

결과

>> 150
6

입력이 150이라면

1. 150 -> 2로 나눠 -> 75

2. 75 -> 3으로 나눠 -> 25

3. 25 -> 3으로 나눠 -> 8

4. 8 -> 2로 나눠 -> 4

5. 4 -> 2로 나눠 -> 2

6. 2 -> 2로 나눠 -> 1

 

---

3. 점화식 및 수열 응용

- a1=1, a2=3

- an = 2*an-1 + 3*an-2

- 종료조건은 주어진 초기값인 n=1, n=2일 때 즉, a1, a2가 된다.

 

def recurrence(n):
    if n==1: return 1
    if n==2 : return 3

    return 2*recurrence(n-1)+3*recurrence(n-2)

print(recurrence(10))

 

결과

19683

 

---

Q) 피포나치 수열

- 피보나치수열 : 이전 두 항의 합이 그다음 항이 되는 수열

- an = an-1 + an-2

- a1=1, a2=1

- 정수 n을 입력. an을 출력하라

 

def fibo(n):
    if n==1 or n==2: return 1
    return fibo(n-1)+fibo(n-2)

n=int(input())
print(fibo(n))

 

결과

>> 5
5

- [1, 1, 2, 3, 5,...]

 

---