재귀

<프로그래머스 고득점kit>

<팩토리얼>

def fact(n):
  if(n<=1):
    return 1
  else:
    return n*fact(n-1)
#
num=int(input())
result=fact(num)
print(result)

<해설>

팩토리얼 5!는 5,4,3....가다가 1에서 멈춰야하기때문에 재귀함수의 끝조건으로 1보다 작음을 선언하고 그것이 아닐 경우엔 곱을 반환한다

<피보나치 수 5>

def fibo(n):
  if(n==0):
    return 0;
  elif(n==1):
    return 1
  else:
    return fibo(n-1)+fibo(n-2)
num=int(input())
print(fibo(num))

<해설>

"현재 피보나치 수는 전 피보나치와 전전 피보나치의 수의 합니다"라는 로직을 그대로 f(n)=f(n-1)+f(-2)로 옮겨보면 return f(n-1)+f(n-2)가 된다.

<예외케이스>0번쨰 수와 1번째 수는 이미 아는 상태에서 시작을 하는 것이기 때문에 미리 n==0,n==1이라는 조건을 주어야 한다.

<우박수>

def ob(num):
  if(num==1):
    print(int(num))
    return 
  elif(num%2==0):
    print(int(num))
    ob(num/2)
  else:
    print(int(num))
    ob(3*num+1)
#
num=int(input())
ob(num)

<해설>

현재의 공식이 항상 참이라는 가정하에 각각을 나누어 재귀한다.마지막에 num==1일경우 바로 더이상 재귀하지않고 끝낸다!