関数ってなんぞ？という方にちょっとだけ。関数とは任意の処理をまとめた塊です。具体的には、

In [1]:
def add(x,y):
    return x+y
In [2]:
add(2,3)
Out[2]:
5

このようにdef ~(~):でpythonでは定義します。今回の関数addは二つの数を足し算するものです。他にもいろいろできます。

In [3]:
def kyopuro():
    print('競プロやりなよ')
    print('あああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ')
    print('U')
In [4]:
kyopuro()

競プロやりなよ
あああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ
U

こんな感じで書きます。
上のaddに出てくるreturnという文字は返り値というものを指定します。うまく説明ができないのでネットでググってください。
一応挙動を見ておくと、

In [5]:
a = 0
print(a)
a = add(114*1000,514)
print(a)

0
114514

こんな感じで返り値が変数に代入されるんですね。こんな挙動をします。あと、returnの所まで来ると関数が終了します。
例えば、

In [6]:
def put():
    print('114',end = '')
    return
    print('514')
In [7]:
put()

114

このように、returnより前の114の出力は実行されますが、後の514の出力は実行されません。

ひとまず関数についての知識はこれぐらいでよいので再帰関数について話していきます。再帰関数は動的計画法という手法や、深さ優先探索の時に使うことができるので知っておくと良いです。
再帰関数とは何かというと、関数の中で自身を呼び出す関数のことです。

In [8]:
def rarara(n):
    if n == 0:return 0
    print('ラララ')
    rarara(n-1)
In [9]:
rarara(5)

ラララ
ラララ
ラララ
ラララ
ラララ

具体的にはこんな感じ。これは引数nの回数だけラララという文字列を出力する関数です。なにが起こってるかがんばって考えたらわかるんじゃないかなあ。下はこの手の話でよくある再帰関数でフィボナッチ数列を求める話。

In [10]:
def fibo(n):  # n個目のフィボナッチ数列を求めます。
    if n == 1:return 0  # フィボナッチ数列の1個目は0
    if n == 2:return 1  #フィボナッチ数列の2個目は1
    return fibo(n-1) + fibo(n-2)  # フィボナッチ数列のn個目はn-1個目とn-2個目を足したもの
In [11]:
fibo(7)
Out[11]:
8
In [12]:
fibo(20)
Out[12]:
4181

実際はこの関数を使うと100番目のフィボナッチ数列を計算するのも相当な時間がかかるのでできません。もうちょっと効率的な方法はそのうち...
最後に最大公約数を求める関数を再帰関数で作ります。

In [13]:
def gcd(a,b):
    if a < b:a,b = b,a  # aがbより小さかったら入れ替え
    if a % b == 0:return b  # aがbで割り切れたらbを返す。＊ここで終了
    else:return gcd(b,a%b)  # 割り切れないときはbとaをbで割ったあまりでの最大公約数を返す。
In [14]:
gcd(5,68)
Out[14]:
1
In [15]:
gcd(348,24)
Out[15]:
12
In [16]:
gcd(24,1283718974102948713483484783694384359162738738970298372960)
Out[16]:
8

こんな感じでめちゃめちゃでかい数に対しても一瞬で求めることができます。中身は高校で習ったユークリッドの互除法ですね。