재귀함수

함수가 자기 자신을 호출하는 ‘재귀(recursion)’  by 위키독스

스택은 deque를 활용해 LIFO(last in first out)/ FIFO(first in first out) 개념을 이해했다.

(물론 아직 시간초과의 문제가 발생하는 것을 보면 그 부분도 추가 정리가 필요하다.

 

그러나 '재귀'는 어렵다. 복잡해지면 2중 3중 for문 구조를 만들던 취코녀에게 더욱 어럽게 느껴진다.

백준 브론즈 레벨에서도 헤매는걸 보면서 실버에 들어가기 전에 한 번 정리하고 넘어가는 게 좋을 거 같다.

재귀의 개념, 지역변수/전역변수 개념, 내가 풀었던 문제를 정리하며 나만의 재귀 cheet sheet를 만들어본다.

 

1. 재귀의 개념

함수 안에서 함수가 자기자신을 호출하는 것

제한을 두지 않으면 계속해서 돌아가는 구조

 

2. 지역변수/전역변수 개념

지역변수 : 함수 안에서 만들어진 변수/ 함수의 실행이 끝나면 없어짐

전역변수 : 함수 밖에서 만들어진 변수/ 함수의 실행이 끝나도 남아있음

출처: 위키독스

 

함수 안에서 global로 전역변수 지정해 줘야 함수 밖에서 해당 변수를 사용할 수 있다.

 

3. 문제풀이

1) https://www.acmicpc.net/problem/27433

27433번: 팩토리얼 2

팩토리얼을 재귀함수로 구현하기

- n! = n*(n-1)! 의 구조를 함수로 만들기

- n이 하나씩 줄어들면서 1보다 작거나 같아지는지 확인하기

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

print(factorial(int(input())))

 

2) https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

피보나치 수를 재귀함수로 구현하기

- Fn = Fn-1 + Fn-2 의 구조로 함수 만들기

- n이 하나씩 줄어들면서 1보다 작거나 같아지는지 확인하기

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

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

 

3) https://www.acmicpc.net/problem/25501

25501번: 재귀의 귀재

재귀함수의 호출 횟수를 구하기

- global을 활용해 전역변수 지정

def recursion(s, l, r):
    global cnt; cnt += 1 #중요!

    if l >= r: return 1
    elif s[l] != s[r]: return 0
    else: return recursion(s, l + 1, r - 1)

def isPalindrome(s):
    return recursion(s, 0, len(s) - 1)

N,*P_list = open(0).read().split()

for p in P_list:
    cnt = 0
    print(isPalindrome(p),cnt)