Java/רקורסיה/תרגילים

רקורסיה פשוטה

הדפסה רקורסיבית

כתבו פונקציה רקורסיבית שתקבל מספר שלם כלשהו (ידוע שאינו שלילי) וסימן (משתנה מטיפוס char), ותדפיס את הסימן כמספר הפעמים שהתקבלו.

פתרון

public static void printer(int n, char c) {
	if(n<=0) return;
	System.out.print(c);
	printer(n-1, c);
}

חזקה

כתבו פונקציה רקורסיבית שתקבל שני מספרים שלמים, ותחזיר את הראשון בחזקת השני. אם מנסים להעלות מספר בחזקת אפס - הפונקציה תחזיר 1. אם מנסים להעלות בחזקה שלילית - הפונקציה תחזיר 0.

פתרון

public static int power(int n, int m) {
	if(m<0) return 0;
	if(m==0) return 1;
	return n * power(n, m-1);
}

אתגר: האם קיימת דרך להעלות מספר בחזקה בעזרת מספר קטן יותר של פעולות? האם תוכלו לעשות זאת בעזרת שיטה רקורסיבית?

רמז

עבור n זוגי מתקיים $({a^{\frac {n}{2}}})^{2}=a^{n}$, ועבור n אי זוגי, ${({a^{\frac {n-1}{2}}})^{2}}\times a=a^{n}$