רקורסיה + תכנות אסינכרוני בNode.js

בעקבות באג שמצאתי אצל לקוח החלטתי לפרסם פוסט מאתגר בעניין רקורסיה ותכנות אסינכרוני. הבעיה היא שרקורסיה היא גם ככה עניין מסובך והתכנות האסינכרוני מוסיף לזה עוד מימד של בעייתיות כיוון שכשהפונקציה קוראת לזו שלאחריה זה לא עובר בstack המסורתי אלא כל פונקציה רצה בקצב שלה.

הנה דוגמה לסדרת פיבונאצ'י הידועה. מימוש רקורסיבי רגיל ולאחריו מימוש עם Promises.

אנחנו נשתמש בrouter של Express לצורך הדוגמה אבל כל אובייקט אחר יתאים גם:

var router = express.Router();

עכשיו לצורה הרקורסיבית הסטנדרטית:

router.fib = function(n) {
	if(n <= 2) {
		return 1;
	} else {
		return this.fib(n - 1) + this.fib(n - 2);
	}
};

והנה המימוש הרקורסיבי-אסינכרוני:

router.fibAsync = function(n) {
	return new Promise(function (resolve, reject) {
		if(n <= 2){
			resolve(1);
		}else{
			var sum = 0;
			router.fibAsync(n-1).then(function(res1){
				sum += res1;
				router.fibAsync(n-2).then(function(res2){
					sum += res2;
					resolve(sum);
				});
			});
		}
	});
};

כפי שניתן לראות המימוש משתמש בPromises והערכים המוחזרים הם הסכום שחוזר בthen של הpromise הרקורסיבי. הדבר היחיד שצריך לזכור בעבודה עם Promises הוא שהערך לא חוזר מהפונקציה כמו בכתיבה רגילה אלא בתוך הthen שהוא למעשה החלופה לCallback המסורבל. הפונקציה fibAsync בעצמה מחזירה Promise כך שיש לקרוא לה בצורה אסינכרונית עם then.

בפוסט הבא נלמד להריץ רקורסיה על עץ כשיש להפעיל לולאה על הבנים והכל כמובן… אסינכרוני!