Recursion
পুনরাবৃত্তি
একটা function যা নিজেকে ছোট input-এ ডাকে। Base case থামায়, recursive case ছোট ফল থেকে বড় ফল বানায়। Induction-এর computational রূপ।
def factorial(n):
if n == 0: return 1 # base case
return n * factorial(n - 1) # recursive caseCorrectness প্রমাণ হয় [[induction]] দিয়ে, আর termination প্রমাণ হয় [[well-ordering-principle]] দিয়ে — argument কঠোরভাবে কমছে এবং অ-ঋণাত্মক।
গাণিতিক induction অসীম পর্যন্ত চলে; বাস্তব recursion সসীম stack-এ চলে। এই ফাঁকটাই stack overflow।
ulimit -s # সাধারণত 8192 KB8 MB stack, প্রতি frame ~32 byte → প্রায় ২,৬০,০০০ frame। তারপর segfault।
Tail call optimization: recursive call-এর পরে আর কোনো কাজ না থাকলে compiler নতুন frame না বানিয়ে বর্তমানটা পুনর্ব্যবহার করতে পারে — recursion কার্যত loop হয়ে যায়।
gcc -O0 prog.c # segfault
gcc -O2 prog.c # চিরকাল চলে — TCO প্রয়োগ হয়েছেScheme, Erlang আর Haskell-এ TCO বাধ্যতামূলক, তাই সেখানে recursion-ই প্রধান loop। Python ইচ্ছাকৃতভাবে করে না — stack trace রক্ষার জন্য।