i can do ik!

1902 : (재귀 함수) 1부터 n까지 역순으로 출력하기

문제 설명

정수 n부터 1까지 출력하는 재귀함수를 설계하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for, while, goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

정수 n이 입력된다(1<=n<=200)

출력

n부터 1까지 한 줄에 하나씩 출력한다.

입력 예시

10

출력 예시

10
9
8
7
6
5
4
3
2
1

풀이

n = int(input())
def func(n):
  print(n)
  if(n!=1):
    func(n-1)
func(n)

1901 : (재귀 함수) 1부터 n까지 출력하기

문제 설명

1부터 정수 n까지 출력하는 재귀함수를 설계하시오.

이 문제는 반복문 for, while 등을 이용하여 풀수 없습니다.

금지 키워드 : for while goto
시간 제한 : 1 Sec
메모리 제한 : 128 MB

입력

정수 n이 입력된다(1<=n<=200)

출력

1부터 n까지 한 줄에 하나씩 출력한다.

입력 예시

10

출력 예시

1
2
3
4
5
6
7
8
9
10

풀이

n = int(input())
def func(n):
  if(n!=1):
    func(n-1)
  print(n)
  
func(n)

재귀란

• 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.

재귀함수란

• 함수가 직접 또는 간접적으로 자신을 호출하는 프로세스.
• 재귀 알고리즘을 이용하면 복잡한 문제들도 간단하게 해결 할 수 있다.
• 호출이 깊어지면 성능의 저하가 있을 수 있다.
• 종료지점을 구현하지 않으면 스택 오버플로우가 발생할 수 있다.

재귀함수 장단점

장점

• 변수의 사용을 줄여준다.
• 코드의 가독성을 높일 수 있다.

단점

• 시간복잡도가 반복문에 비해 계산이 어렵다.
• 반복문보다 메모리 사용량이 많고 수행 시간이 더 길어질 수 있다.
• 함수 호출을 많이 하기에 StackOverFlow의 가능성이 잇다.
• 종결조건을 정하지 않으면 무한 반복이 일어난다.

재귀함수 사용의 예

• 1부터 n까지의 합
• ! 팩토리얼
• 최대공약수 문제
• 피보나치 수열 구하기
• 문자열의 길이를 구하는 등의 문제
• 2진수 변환하기 문제
• 배열 총합 문제