מבוא לתכנות ולמדעי המחשב בשפת C/דוגמה גאומטרית, רקורסיה (עצרת)

דוגמה גאומטרית

בדוגמה זו ננסה להמחיש את הכוח שיש בהגדרת פונקציות המבצעות משימות קטנות ומוגדרות היטב. לסוג התכנות הזה קוראים תכנות פרוצדורלי - תכנות הבנוי מאוסף פרוצדורות (פונקציות ב C).

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

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

#include <stdio.h> 
 
int ROWS = 40, COLS = 70; 
char board[40][70];  
// initializes the board's content 
void initBoard() {
    int i,j; 
    for(i=0; i<ROWS; ++i)
	for(j=0; j<COLS; ++j)
	    board[i][j] = '.'; 
}

// display the board 
void printBoard() {
    int i,j; 
    for(i=0; i<ROWS; ++i) {
	for(j=0; j<COLS; ++j)
	    printf("%c",board[i][j]); 
	printf("\n"); 
    }
}
 
//draw an upright rectangle on the board
// leftX is the leftmost x coordinate
// topY is the topmost y coordinate
// hence (leftX; topY) is the top-left corner of the rectangle
// ch is the fill character
void drawRectangle(int leftX, int topY, int breadth, int height, char ch) {
    int i,j; 
    for(i=leftX; i<leftX+breadth; ++i)
	for(j=topY; j<topY+height; ++j)
	    board[i][j] = ch;
 
}

int main() {
    initBoard(); 
    drawRectangle(2,2,10,6,'@'); 
    drawRectangle(10,20,10,20,'+'); 
    printBoard(); 
    return 0;
}

פלט:

......................................................................
......................................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@..............................................................
..@@@@@@............++++++++++++++++++++..............................
..@@@@@@............++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
....................++++++++++++++++++++..............................
......................................................................
......................................................................

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

משולש וריבוע

כעת נוסיף פונקציה המציירת ריבוע ומסתמכת על הפונקציה הקיימת לציור מלבן. כמו כן נוסיף פונקציה המציירת משולש שווה שוקיים ופונקציית main שבודקת את פעולתן:

// draw a square on the board
// (leftX, topY0) is the top-left corner of the square
// ch is the fill character
void drawSquare(int leftX, int topY, int size, char ch) {
    drawRectangle(leftX,topY,size,size,ch); 
}

// draw an upright isosceles triangle on the board    
//(topX, topY) is the topmost point of the rectabgle
void drawTriangle(int r, int c, int base, char ch) {
    int i,j; 
    for(i=0; i<base; ++i)
	for(j=-i; j<1+i; ++j)
	    board[i+r][c+j] = ch; 
}
 
int main() {
    initBoard(); 
    drawTriangle(10,30,7,'*'); 
    drawSquare(20,10,15,'='); 
    printBoard(); 
    return 0;
}

פלט:

......................................................................
......................................................................
..............................*.......................................
.............................***......................................
............................*****.....................................
...........................*******....................................
..........................*********...................................
.........................***********..................................
........................*************.................................
......................................................................
......................................................................
......................................................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
..........===============.............................................
......................................................................

הגדרת בית

מאחר שיש לנו צורה של מלבן ומשולש, אפשר בעזרתם להגדיר ציור של בית:

void drawHouse(int r, int c, int size, int ch) {
    drawTriangle(r,c,size,ch);
    drawRectangle(r+size,c-size/2,size-1,size+1,ch); 
}
 
int main() {
    initBoard(); 
    drawHouse(20,20,8,'*'); 
    printBoard(); 
    return 0;
}

פלט:

......................................................................
....................*.................................................
...................***................................................
..................*****...............................................
.................*******..............................................
................*********.............................................
...............***********............................................
..............*************...........................................
.............***************..........................................
................*********.............................................
................*********.............................................
................*********.............................................
................*********.............................................
................*********.............................................
................*********.............................................
................*********.............................................
......................................................................

הגדרת רחוב

ואם יש גם בית, אפשר להגדיר רחוב:

void drawStreet(int r, int c, int size, int ch, int n) {
    int i,gap = 3; 
    for(i=0; i<n; ++i) 
	drawHouse(r,c+(2*size+1+gap)*i,size,ch); 
}
 
int main() {
    initBoard(); 
    drawStreet(20,10,4,'*',5); 
    printBoard(); 
    return 0;
}

פלט:

......................................................................
..........*...........*...........*...........*...........*...........
.........***.........***.........***.........***.........***..........
........*****.......*****.......*****.......*****.......*****.........
.......*******.....*******.....*******.....*******.....*******........
........*****.......*****.......*****.......*****.......*****.........
........*****.......*****.......*****.......*****.......*****.........
........*****.......*****.......*****.......*****.......*****.........
......................................................................

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

בדיקת חריגה

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

void plot(int r, int c, char ch) {
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS)
	return; 
    board[r][c] = ch; 
}

ואז נשכתב את פונקציית המלבן, לדוגמה, באופן הבא:

void drawRectangle(int r, int c, int sizeR, int sizeC, char ch) {
    int i,j; 
    for(i=r; i<r+sizeR; ++i)
	for(j=c; j<c+sizeC; ++j)
	    plot(i,j,ch);
 
}

הקוד בשלמותו

הקוד שלנו, אחרי כל ההוספות והשינויים, נראה עכשיו כך:

#include <stdio.h> 
 
int ROWS = 40, COLS = 70; 
char board[40][70];  
 
void plot(int r, int c, char ch) {
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS)
	return; 
    board[r][c] = ch; 
}
 
void initBoard() {
    int i,j; 
    for(i=0; i<ROWS; ++i)
	for(j=0; j<COLS; ++j)
	    board[i][j] = '.'; 
}
 
void printBoard() {
    int i,j; 
    for(i=0; i<ROWS; ++i) {
	for(j=0; j<COLS; ++j)
	    printf("%c",board[i][j]); 
	printf("\n"); 
    }
}
 
void drawRectangle(int r, int c, int sizeR, int sizeC, char ch) {
    int i,j; 
    for(i=r; i<r+sizeR; ++i)
	for(j=c; j<c+sizeC; ++j)
	    plot(i,j,ch);
 
}
 
void drawSquare(int r, int c, int size, char ch) {
    drawRectangle(r,c,size,size,ch); 
}
 
void drawTriangle(int r, int c, int size, char ch) {
    int i,j; 
    for(i=0; i<size; ++i)
	for(j=-i; j<1+i; ++j)
	    plot(i+r, c+j, ch); 
}
 
void drawHouse(int r, int c, int size, int ch) {
    drawTriangle(r,c,size,ch);
    drawRectangle(r+size,c-size/2,size-1,size+1,ch); 
}
 
void drawStreet(int r, int c, int size, int ch, int n) {
    int i,gap = 3; 
    for(i=0; i<n; ++i) 
	drawHouse(r,c+(2*size+1+gap)*i,size,ch); 
}
 
int main() {
    initBoard(); 
    drawStreet(20,2,6,'O',5); 
    drawStreet(10,3,4,'@',6); 
    drawRectangle(32,1,3,68,'=');
    drawTriangle(0,35,10,'*'); 
    printBoard(); 
 
    return 0;
}

פלט:

...................................*..................................
..................................***.................................
.................................*****................................
................................*******...............................
...............................*********..............................
..............................***********.............................
.............................*************............................
............................***************...........................
...........................*****************..........................
..........................*******************.........................
...@...........@...........@...........@...........@...........@......
..@@@.........@@@.........@@@.........@@@.........@@@.........@@@.....
.@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@....
@@@@@@@.....@@@@@@@.....@@@@@@@.....@@@@@@@.....@@@@@@@.....@@@@@@@...
.@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@....
.@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@....
.@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@.......@@@@@....
......................................................................
......................................................................
......................................................................
..O...............O...............O...............O...............O...
.OOO.............OOO.............OOO.............OOO.............OOO..
OOOOO...........OOOOO...........OOOOO...........OOOOO...........OOOOO.
OOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO
OOOOOOO.......OOOOOOOOO.......OOOOOOOOO.......OOOOOOOOO.......OOOOOOOO
OOOOOOOO.....OOOOOOOOOOO.....OOOOOOOOOOO.....OOOOOOOOOOO.....OOOOOOOOO
OOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO
OOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO
OOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO
OOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO
OOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO.........OOOOOOO
......................................................................
.====================================================================.
.====================================================================.
.====================================================================.
......................................................................
......................................................................
......................................................................
......................................................................

תכנון מלמטה למעלה ומלמעלה למטה

בדוגמה האחרונה, בנינו כלים בסיסיים ועליהם בנינו כלים מורכבים יותר שמסתמכים על הכלים הקיימים. תכנון כתיבת קוד בסדר הזה נקרא bottom up design - תכנון מלמטה למעלה. תכנון הקוד הזה עלול להיות בעייתי. איך נדע מראש בדיוק לאיזה כלים בסיסיים נזדקק על מנת לפתור שאלה מורכבת? אולי אחרי שנכתוב את הפונקציות הבסיסיות שלנו, נגלה שלא את כולן אנחנו באמת צריכים? אולי נגלה שעל מנת לפתור את הבעיה המרכזית, עדיף היה לכתוב את הכלים הבסיסיים עם פרמטרים אחרים?

בגלל סיבות אלה, נוטים לפעמים להתחיל מכתיבת הפונקציות הראשיות. נניח שאת הדוגמה האחרונה היינו מתחילים לכתוב דווקא מהפונקציה שמגדירה רחוב:

void drawStreet(int r, int c, int size, int ch, int n) {
    int i,gap = 3; 
    for(i=0; i<n; ++i) 
	drawHouse(r,c+(2*size+1+gap)*i,size,ch); 
}

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

כתיבה כזו של תוכנה, שמתחילה מפונקציות ראשיות ורק אחר כך נגשת לכתיבת הפונקציות שעליהן היא מסתמכת, נקראת top down design - תכנון מלמעלה למטה. היתרון הגדול שלו הוא, כאמור, שהצורך מכתיב את הפונקציות שאנו מממשים. תכנון כזה של תוכנה, מביא הרבה פעמים לפתרונות אלגנטיים יותר. תכנון מלמטה למעלה מביא לעיתים לפתרונות שנראים מסורבלים ומלאכותיים יותר.

מכיוון ש ב- top down design אנו קוראים לפונקציות שאינן קיימות, סגנון כתיבה זה דורש אמונה וביטחון ביכולת שלנו לממש את הפונקציות שאותן עדיין לא כתבנו. הביטחון הזה מגיע עם הנסיון ולכן טכניקה של כתיבה מלמעלה למטה היא משהו ששואפים להגיע אליו עם פיתוח מיומנות התיכנות, לאו דווקא בהתחלה.

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

רקורסיה

ראינו ששימוש בפונקציות מאפשר לנו לפתור בעיה גדולה ע"י פירוק שלה לבעיות משנה:

void problem(..) {
    subProblem1(..); 
    subProblem2(..); 
    ..
}

לאחר כל פתרון של בעיית משנה, ממשיכים להתמודד עם הבעיה הראשית. בדוגמה הגאומטרית, בשביל לצייר בית, פתרנו שתי בעיות משנה - ציור מלבן וציור משולש.

לפעמים בעיית המשנה היא בעיה פשוטה יותר אבל מאותו סוג. לדוגמה, בשביל למצוא את הערך של !n אפשר למצוא את הערך של !(n-1) ולהכפיל ב n:$n!=(n-1)!\cdot n$. מכיוון שבעית המשנה היא בעיה מאותו הסוג, רק עם פרמטר שונה, אפשר לתת לאותו קוד לטפל בה. מכיוון שמדובר באותו קוד, גם הוא ינסה לפתור אותה ע"י פתירת בעיית משנה פשוטה יותר - !(n-2). כמובן, שאם תמיד הקוד ינסה לפתור את הבעיה ע"י פתרון של בעיה אחרת, התהליך לא יסתיים לעולם. לכן, בשביל בעיה פשוטה במיוחד, נספק פתרון מן המוכן. במקרה זה נוכל נגיד שאם הקוד מתבקש לחשב את !1 הוא לא ינסה לפתור בעית משנה אלא יתן פשוט את התשובה - 1.

הנה הקוד שמבצע כל זאת:

#include <stdio.h> 

int factorial(int n) {
    if (n == 1) 
	return 1; 
    int rec = factorial(n-1); 
    int ret = n * rec; 
    return ret; 
}

int main() {
    printf("7! = %d \n",factorial(7)); 
    return 0; 
}

פלט:

7! = 5040

ראשית, כדאי לנסות להשתכנע שהקוד של factorial עובד על בעיות פשוטות. נחשוב מה קורה כשמפעילים אותו כך:

factorial(1);

במקרה זה ברור שה if הראשון יצליח והתשובה הנכונה תוחזר מיד. כעת נחשוב על הפעלה כזו:

factorial(2);

בשלב הראשון ה if יכשל ובשורה 6 תתבצע קריאה לחישוב העצרת של 1. כבר השתכנענו שהפעלה כזו של הפונקציה עובדת כהלכה לכן ל rec יושם הערך השווה לעצרת של 1. בשורה הבאה יוכפל הערך הזה ב 2 והתשובה 2 תוחזר כתשובה לשאלה מה העצרת של 2.

באותו אופן, אם אנחנו כבר מאמינים שעצרת של 2 מחושבת כהלכה, קל להשתכנע שחישוב העצרת של 3, המסמך עליה, מחושב גם הוא כהלכה.

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

יש לשים לב לנקודה חשובה: לכל הפעלה של factorial יש את המשתנים הלוקאליים שלה. כאשר מבקשים לחשב את העצרת של 3, הפונקציה נעצרת בשורה 6 על מנת לקרוא לחישוב העצרת של 2. בשלב זה מופעלת factorial אחרת בעלת n=2, rec=1 ו - ret=2. אלה משתנים שונים מאלה של הפונקציה שמנסה לחשב את העצרת של 3. אצלה n=3 ו ret ,rec עדיין לא הושמו כלל. בגלל עובדה זו, במהלך החישוב העצרת של n, כאשר מחשבים את העצרת של 1, קיימים בזיכרון המחשב n מופעים שונים של המשתנים הלוקאליים.

למעשה לא היינו זקוקים למשתנים הלוקאליים והיינו יכולים לכתוב את הקוד גם כך:

int factorial(int n) {
    if (n == 1) 
	return 1; 
    return factorial(n-1)*n; 
}

אבל גם בגרסה זו יש מופעים רבים של המשתנה n.

הפעלה של פונקציה מתוך אותה פונקציה נקראת "קריאה רקורסיבית" ואלגוריתם שמכיל קריאה רקורסיבית נקרא אלגוריתם רקורסיבי או פשוט רקורסיה.

תבנית:ניווט מבוא