★Recursion Upper-Beginner - 3 Solved★

★ 10870 피보나치 수 5 ★

 

def fibo(n):
    if n in [0,1]:
        return n
    else:
        return fibo(n-1) + fibo(n-2)

print(fibo(int(input())))

 

🌺 재귀를 이용해서 함수 안에 그 이전 두 동일한 함수를 또 넣어 재귀적으로 계속 함수 결과가 쌓인 최종 합은 곧 피보나치의 수가 됨

 

※ 주의! n이 20보다 작거나 같으므로 재귀로 사용 가능하나(재귀의 예시를 보여주기 위해 재귀로 풀었을 뿐), n이 매우 큰 수일경우 recursion 깊이가 너무 깊어 error 발생. 이럴 때는 dp를 해결하거나 추가적인 알고리즘 장치로 해결 해야함. 별도 포스팅 참조 필요 ※

---

★ 5956 Symmetry ★

def get_cows(n,m,times,cows):
    if n%2==0 or m%2==0:
        print(cows)
        return
    cows += times
    get_cows(n//2,m//2,times*4,cows)
    
N,M=map(int,input().split()) 
get_cows(N,M,1,0)

 

🌺 recursion에서 주의해야 할 점은, loop에서 겹겹이 쌓인 cycle을 벗어나면서 도로 다시 count될 수 있다는 점! 따라서, recursion이 점점 진행되면서 - 누적되어 더해진 cows 값을 종료 조건에 print해주고 바로 return해 밖으로 나갈 수 있게 해주는 recursion도 만들 수 있다!

 

🌺

① 단 한 변이라도 짝수 길이라면 cow를 생성할 수 없으므로 종료 조건 만들기

② cows와 곱해지는 횟수 times 두 변수가 recursion을 거치면서 값이 달라지므로 모두 recursion 함수 인자에 넣는다.

③ 각 두 변을 2로 나눈 몫으로 이루어진 4개의 정사각형들(recursion 함수)에서 계속 cows 변수에 더하면서 cows 누적합 결과를 재귀결과로 print!

---

★ 25501 재귀의 귀재 ★

import sys
input=sys.stdin.readline

def recursion(string, start, end):
    global cnt
    if start>=end:
        return 1
    elif (string[start] != string[end]):
        return 0
    else:
        cnt+=1
        return recursion(string, start+1, end-1)
    
for _ in range(int(input())):
    letter=input().rstrip()
    cnt = 1
    print(recursion(letter,0,len(letter)-1),cnt)

🌺 그대로 구현. return 종료문이 2개 있고, return문으로 그 다음 재귀함수를 또 호출하는 방식으로 진행

---