תקציר שימושי מחשב, סמסטר ב תשעג, גיא בלשר, רקורסיה

חזרה לקישורים לתקצירים

הקדמה

מתוך פונקציה שאנו מגדירים ניתן לקרוא לעצמה.

ברקורסיה חשוב לזכור:

1. תנאי עצירה
2. "צעד" הרקורסיה - זימון הפעולה בתוך עצמה

תרגילים

תרגיל 1 - חישוב עצרת

נזכור כי:
$\left\{\begin{matrix}n!=\left ( n-1 \right )!\cdot n \\ 0!=1 \ \ \ \ \ \ \ \ \ \ \ \ \end{matrix}\right.$

ונכתוב פונקציה מתאימה:

(function [f] = fact (n
if n==0
   ;f=1
else
   ;(f=n*fact(n-1
end
end

תרגיל 2 - מקדמים בינומיים

המקדם הבינומי $\binom{n}{k}$ מונה כמה אפשרויות יש לנו לבחירת $k$ איברים מתוך $k$ ללא בחירת איבר פעמיים וללא חשיבות לסדר.

נוסחה סגורה לחישוב: $\binom{n}{k}=\frac{n!}{k!\left ( n-k \right )!}$

ממשולש פסקל אנו מקבלים נוסחת נסיגה לחישובם: $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$.

נכתוב פונקציה מתאימה:

(function [b] = binomial (n,k
if k==0 || k==n
   ;b=1
else
   ;(b=binomial(n-1,k)+binomial(n-1,k-1
end
end

תרגיל 3 - איחוד מערכים ממוינים

המטרה: לאחד שני מערכים ממוינים u,v למערך ממוין

הפונקציה המתאימה:

(function [w] = merge (u,v
;(nu=length(u
;(nv=length(v
;nw=nu+nv
;(w=zeros(nw,1
if nu==0
   ;w=v
elseif nv==0
   ;w=u
else
   ;ku=1
   ;kv=1
   for kw=1:nw
      ((if (ku<=nu) && (kv>nv || u(ku)<v(kv
         ;(w(kw)=u(ku
         ;ku=ku+1
      else
         ;(w(kw)=v(kv
         ;kv=kv+1
      end
   end
end
end

תרגיל 4 - מיון מערך

המטרה: למיין מערך ביעילות $O(n\cdot\ln n)$

הביצוע: כל פעם נחלק לשני תת־מערכים, נמיין אותם ונאחד (באמצעות הפעולה מתרגיל 3)

הפונקציה המתאימה:

(function [w] = mergeSort (v
;(n=length(v
if n<=1
   ;w=v
else
   ;(m=floor(n/2
   ;((w1=mergeSort(v(1:m
   ;((w2=mergeSort(v(m+1:n
   ;(w=merge(w1,w2
end
end