প্রাকৃতিক সংখ্যা (Natural Numbers) = ১, ২, ৩, ৪, ... প্রথম n প্রাকৃতিক সংখ্যার যোগফল = n(n+1)/2। কিন্তু রিকার্সন দিয়ে বের করা যায়।
উদাহরণ কোড
#include <iostream>
using namespace std;
int sum(int n) {
if (n == 0)
return n;
else
return n + sum(n - 1);
}
int main() {
int n = 10;
cout << "Sum of first " << n << " natural numbers is " << sum(n);
return 0;
}আউটপুট
Sum of first 10 natural numbers is 55
ব্যাখ্যা
রিকার্সিভ ফাংশন sum(n)
if (n == 0) return 0;— বেস কেস।return n + sum(n-1);— n যোগ করে ছোট সমস্যা সমাধান।
এক্সিকিউশন ট্রেস
sum(10) → 10 + sum(9) → 10+9+sum(8) ... → 10+9+...+1+sum(0) → 55।
তুলনা: ফর্মুলা n*(n+1)/2 O(1) টাইমে কাজ করে। রিকার্সন O(n) টাইম এবং O(n) স্ট্যাক স্পেস নেয়। শুধু শিক্ষামূলক উদ্দেশ্যে রিকার্সন দেখানো হয়েছে।
