[코드트리] 재귀함수를 이용한 3n + 1 수열 / 재귀함수

https://www.codetree.ai/missions/5/problems/3n+1-sequence-with-recursive-function?&utm_source=clipboard&utm_medium=text

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

재귀함수를 이용한 3n + 1 수열

---

 

자연수 n이 주어집니다. n에서 시작하여 n이 짝수면 2로 나누고, n이 홀수면 3을 곱하고 1을 더하는 것을 n이 1이 되기 전까지 계속 반복하려고 합니다. 총 몇 번을 반복해야 1이 되는지를 계산하는 프로그램을 작성해보세요. 단, 재귀함수를 이용하여 문제를 해결해주세요.

 

입력 형식

첫 번째 줄에 정수 n이 주어집니다.

• 1 ≤ n ≤ 100

출력 형식

첫 번째 줄에 1이 되기까지 몇 번을 반복해야하는지 출력합니다.

 

입출력 예제

예제1

입력:

3

출력:

7

 

 

 

내가 짠 코드

---

n = int(input())

def f(n):
    if n==1:
        return 0
    if n%2==0:
        #짝수
        return f(n//2) + 1
    else :
        return f(n*3+1) + 1


print(f(n))

이 문제에서는 1이 될때까지 재귀함수가 호출된 횟수를 카운팅해야한다.

베이스케이스에 대해 만약 1일 경우는 0을 리턴한다. 횟수가 0이므로 

그리고 만약  재귀함수가 호출될때는 리턴값에 f(n//2) + 1 을 하거나 f(n*3+1) + 1 을 한다면 다음 재귀 호출 + 1 을 리턴한다. 이 때 홀수일 때와 짝수일 때를 다르게 호출해야한다.