「再帰」の説明の一例（プログラミング初心者向け）

（Twitterから参照するためのメモです）
まずそもそも「関数」は「同じ形の計算を何度も書かないための仕組み」であることを十分に理解する（させる）。その上で、

sum(0) = 0
sum(1) = 0+1
sum(2) = 0+1+2
sum(3) = 0+1+2+3
sum(4) = 0+1+2+3+4
...

も「同じ計算を何度も書いている」から、

sum(0) = 0
sum(1) = sum(0)+1
sum(2) = sum(1)+2
sum(3) = sum(2)+3
sum(4) = sum(3)+4
...

と書き換える。これを一般化すると

sum(0) = 0
sum(n) = sum(n-1)+n （n>0の場合）

つまり

sum(n) = if n=0 then 0 else sum(n-1)+n

となる

追記：n<0の場合は気にするな。