遞迴(Recursion)的概念是將一個大的問題，分割成許多小問題 去解決。而從程式設計角度來看，函式不單只能被其他函式呼叫，也能被它自己呼叫 ，也就是在一個函式當中呼叫它自己，即為遞回函式（Recursive Function）。

def fun(n):
    if n == 0 or n == 1:
        return n
    else:
        return fun(n-2)+fun(n-1)
a=int(input())
print(a,':',fun(a))
#0:0
#1:1
#2:1
#3:2
#4:3
#5:5
#6:8
#7:13
#8:21
#the number is the sum of the both previous number

使用遞迴計算十進制轉二進制的值：

def fun(n):
    if 2>n:
        return str(n)
    else:
        x=n//2
        r=str(n%2)
        return fun(x)+r
a=int(input())
print(a,':',fun(a))
#eg
#2|13   
#2|6 ...1
#2|3 ...0
#  1 ...1

使用遞迴計算十進制轉k進制的值：

def fun(n,k):
    if k>n:
        return str(n)
    else:
        x=n//k
        r=str(n%k)
        return fun(x,k)+r
a=int(input())
s=int(input())
print(a,':',fun(a,s))

使用遞迴計算最大公因數：

def fun(m, n):
    if m%n==0:
        return n
    else:
        return fun(n,m%n)

a=int(input())
b=int(input())
print(fun(a,b))