[Python] 재귀 함수 - Return Value. 문제풀이 (홀수짝수 합, 최대최소, 점화식, 최소공배수)

1. 홀수끼리 짝수끼리

- 정수 n을 입력

- n이 홀수면 1~n까지 홀수의 합을 출력

- n이 짝수면 2~n까지 짝수의 합을 출력

 

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

n=int(input())
print(odd_or_even_sum(n))

 

결과

>> 7
16

>> 10
30

 

- 홀수일 경우 1부터 n까지의 홀수 합이므로 n+(1부터 n-2까지의 합)으로 나타낼 수 있다.

- n이 2씩 감소하여, n이 1일 경우 1부터 1까지 홀수 합이므로 1을 반환하고 이는 홀수일 때 종료 조건이 된다.

- 짝수일 경우 2부터 n까지의 홀수 합이므로 n+(2부터 n-2까지의 합)으로 나타낼 수 있다.

- n이 2씩 감소하여, n이 2일 경우 2부터 2까지 짝수 합이므로 2를 반환하고 이는 짝수일 때 종료 조건이 된다.

 

---

 2. 최대 최소 구하기

- 정수 n과 n개의 숫자를 입력

- 재귀함수를 이용하여 최댓값과 최솟값을 출력하라

 

def max_value(n):
    if n==1: return arr[n-1]
    return max(max_value(n-1),arr[n-1])

def min_value(n):
    if n==1: return arr[n-1]
    return min(min_value(n-1),arr[n-1])

n=int(input())
arr=list(map(int,input().split()))
print(max_value(n))
print(min_value(n))

 

결과

>> 5
>> 6 7 3 4 9
9
3

 

- n개의 숫자를 가진 배열이 있다고 하면 최댓값은 1번째부터 n-1번째에 있는 숫자 중 최댓값과 배열의 n번째 수와 비교를 하여 더 큰 숫자가 n개의 숫자 중 최댓값이 된다.

- 최솟값도 이와 같은 방법을 이용한다.

- n=1이면 배열에 존재하는 1개의 수가 최댓값 또는 최솟값이 되므로, 이는 종료 조건이 된다.

 

---

3. 점화식을 사용한 계산 횟수

- 자연수 n을 입력

- n이 짝수면 2로 나누고, n이 홀수면 3을 곱해 1을 더한다.

- n이 1이 되면 1이 되기까지 계산 횟수를 출력하라

 

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

print(function(int(input())))

 

결과

>> 6
8

 

1. 6은 짝수 -> 2로 나누면 -> 3

2. 3은 홀수 -> 3을 곱해 1 더하면 -> 10

3. 10은 짝수 -> 2로 나누면 -> 5

4. 5는 홀수 -> 3을 곱해 1 더하면 -> 16

5. 16은 짝수 -> 2로 나누면 -> 8

6. 8은 짝수 -> 2로 나누면 -> 4

7. 4는 짝수 -> 2로 나누면 -> 2

8. 2는 짝수 -> 2로 나누면 -> 1

따라서 1이 되기까지 계산 횟수는 8번이다.

- function(n) 함수는 횟수를 반환해야 한다.

- n이 짝수 또는 홀수에 따라 function(n//2) 또는 function(3*n+1)의 횟수에 1을 더한다.

- n=1일 때는 함수를 종료시키고 횟수에 포함되지 않으므로 0을 반환시킨다.

 

---

4. 최소공배수

- 자연수 n과 n개의 수를 입력.

- n개의 숫자들의 최소공배수를 출력하라.

 

def lcm(a,b):
    for i in range(1,a+1):
        if b*i%a==0: return b*i 

def lcm_arr(n):
    if n==1:
        return arr[n-1]
    return lcm(lcm_arr(n-1),arr[n-1])

n=int(input())
arr=list(map(int,input().split()))
print(lcm_arr(n))

 

결과

>> 5
>> 6 7 9 3 4 
252

 

1. lcm(a, b)

- 두 수 a, b의 최소 공배수를 구하는 함수

- for문을 사용하여 i의 범위를 1부터 a까지 한다.

- i를 순차적으로 증가하며 b*i가 a의 배수인지 확인한다.

- 배수이면 b*i가 최소공배수이므로 b*i를 반환한다.

2. lcm_arr(n)

- n개의 숫자들의 최소공배수를 반환하는 함수

- 1번째부터 n-1번째 수까지의 최소공배수 (lcm_arr(n-1))와 n번째 수의 최소공배수는 n개의 숫자들의 최소공배수와 같다.

- n=1인 경우 배열 내에 있는 1개의 숫자가 최소공배수이므로 그 수를 반환한다. (종료 조건)

 

---