[코드트리] 재귀함수를 이용한 최댓값 / 재귀함수

 

 

https://www.codetree.ai/missions/5/problems/maximum-value-with-recursive-function?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 재귀함수를 이용한 최댓값

---

n개의 원소 중 최댓값을 구하는 프로그램을 작성해보세요. 단, 재귀함수를 이용하여 문제를 해결해주세요.

 

입력 형식

첫 번째 줄에 정수 n이 주어집니다. 두 번째 줄에 n개의 정수가 주어집니다.

• 1 ≤ 원소의 범위 ≤ 100

• 1 ≤ n ≤ 100

출력 형식

첫 번째 줄에 주어진 원소 중 최대값을 출력합니다.

입출력 예제

예제1

입력:

6
1 5 7 9 2 6

 

출력:

9

 

 

내가 짠 코드

---

import sys

n = int(input())
arr = list(map(int, input().split()))
x = -99999
def f(n):
    if n==0:
        return max(arr[0], x)
    
    return max(f(n-1), arr[n])

print(f(n-1))

이번 문제는 배열에서 가장 최대값을 출력해야하는데 재귀적으로 풀어야한다. 

재귀함수이므로 베이스케이스를 생각해보자.

 

베이스케이스는 n==0 일때로 -1번째 원소로는 접근하면 안되므로 이에 대해 따로 처리가 필요하다. 0일때는 0을 값을 출력하도록 해준다. 

 

그 후 재귀적 처리를 위해 n번째 원소와 n-1번째까지 누적돼서 결정된 max 와 비교한다.

1일때는 arr[0] 와 arr[1] 을 비교할 것이고, 2일 때는 arr[2] 와 지금까지 max 를 비교할 것이고 이런식으로 n 까지 갈것이다.

 

주의할 점은 프린트할 때 f(n-1) 을 넣어야한다. 배열의 인덱스는 n번째가 n-1 이기 때문이다.