vahid
بي تو هرگز
Joined: 26 Nov 2004
Posts: 3067
Location: Tehran
|
 Posted: Tue Dec 14, 2004 9:57 pm Post subject: recursive functions توابع بازگشتي23 آذرماه |
 |
|
برنامه اي بنويسيد كه توسط تابعي به نام fact براي محاسبه فاكتوريل يك عدد صحيح مقدار n! را ( n را از ورودي بگيرد و ) محاسبه كند و در خروجي بنويسد :
|
#include <stion.h>
#include <conio.h>
long int fact(int);
main(){ int x;
printf("Enter An Integer ");
printf("value:");
scanf("%d",&x);
printf("\n fact(%d)=%d",x,fact(x));
return 0; }
long int fact(int n){
long int p=1;
while(n>1){
p*=n;
n--;}
return(p); }
|
توابع بازگشتي ( recursive functions )
تابع بازگشتي را تابعي گوييم كه خود را صدا ميزند ( فراخواني ميكند ) و به خودش باز ميگردد . توضيحات متعاقبا داده خواهد شد .
پياده سازي :
تعريف مساله را به فرم بازگشتي روي كاغذ پياده سازي ميكنيم .
هر تعريف بازگشتي شامل حداقل دو بخش زير است :
الف) بخش بازگشتي ( خودفراخوان recursive )
ب) شرط خاتمه ( فراخوانيها )
مراحل فوق را براي برنامه فوق كه فاكتوريل بود طي ميكنيم :
|
1) n * ( n-1 ) ! , n>1
2) 1 , else
|
دو مرحله فوق مربوط به تابع !n است .
مثال) تابع فاكتوريل را به صورت بازگشتي پياده سازي كنيد .
| long int fact(int n) {
if(n) return(n*fact(n-1));
return(1); }
|
trace تابع فوق را براي عدد سه انجام دهيد :
|
n fact(n)
-----------------
3 3*fact(3-1)
2 2*fact(2-1)
1 1*fact(1-1)
|
مثال) اگر فرض كنيم n عددي زوج است تابعي پياده سازي كنيد بصورت بازگشتي كه مجموع اعداد زوج بين صفر و n را محاسبه كند .
|
1) n+s(n-2) , n>0
2)sum=0 , n=0
|
|
int sum(int n) {
if (n) return(n+sume(n-2));
return 0; }
|
حالات خاص :
الف) وقتي در بخش بازگشتي تعريف بيش از يك فراخواني از تابع داشته باشيم ( فراخواني ها تشكيل درخت k تايي ميدهند ) كه k تعداد فراخواني ها است .
مثال) بدون پياده سازي به زبان c بازاي n=5 مقدار f(n) صورت زير را بدست آوريد :
|
1) f(n-1)+f(n-2) , n>1
2)n , n<=1
|
|
f(5)
__/\____
____/ \_
/ \
f(4) + 2*f(3)
| \
| \
f(3)+2*f(2) f(2)+2f(1)
|
|
f(2)+2*f(1)
|
|
f(1)+2*f(0) |
ب) وقتي بيش از يك پارامتر داشته باشيم :
|
1)f(n-2,m-1) , m+n>0
f(n,m)=
2) m+n , m+n<=0
|
مثال) مقدار تابع فوق را بازاي n=5 و m=3 بدست اوريد :
|
I. f(5,3)=f(3,2)-2
II. f(3,2)=f(1,1)-1
III. f(1,1)=f(-1,0)
IV. f(-1,0)=-1
|
| Quote: |
تمرين 1 ) پراسيجري بنويسيد كه يك رشته را بصورت معكوس در خروجي چاپ كند ( با تابع بازگشتي )
تمرين 2) تعريف بازگشتي ذكر شده در نمونه ب از حالات خاص را بصورت يك تابع پياده سازي كنيد .
تمرين 3) تابعي براي محاسبه k جمله اول سري فيبوناچي بنويسيد ( بصورت بازگشتي مجموع ارقام را نمايش دهد )
تمرين 4) سري(sin(x را بصورت يك تابع بازگشتي در خروجي بنويسيد k جمله اول انرا در خروجي بنويسيد و x را بگيرد و محاسبه كند .
| | sin(x)=x-(x^3/3!)+(x^5/5!)-... |
|
|
|
Profile 
Log in to check your private messages | 
FAQ 
Search 
Memberlist 
Usergroups 
Log in
Register
