מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מציאת סיבוכיות פסוודו-קוד/תרגילים/פונקציה המשתמשת במודולו/שאלה

להלן פסוודו-קוד לפונקציה Foo, המקבלת מספר שלם לא-שלילי ומחזירה מספר שלם:

Foo(n)
1	if n == 0
2		return 0

3	return n % 2 + Foo( ⌊n / 2⌋ )

אנא הסבר מה עושה הפונקציה (בלווי נימוק), ונתח את סיבוכיותה.