Skip to content

Commit 7ba97e9

Browse files
author
Saeid Darvish
committed
complete recursive
1 parent 45ee4b9 commit 7ba97e9

2 files changed

Lines changed: 107 additions & 1 deletion

File tree

‎_static/l14-fibonacci-relation.png‎

2.46 KB
Loading

‎lessons/l14.rst‎

Lines changed: 107 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -74,7 +74,48 @@
7474
* یک عبارت حاوی فراخوانی خود تابع
7575
* یک شرط برای انتخاب بین فراخوانی مجدد و پایان
7676

77-
**پیاده‌سازی شیوه بازگشتی شاید به نظر هیجان‌انگیز باشد اما نباید فراموش کرد که میزان حافظه (Memory) زیادی مصرف می‌کند، اجرای آن زمان‌بر خواهد بود، درک جریان اجرای آن اغلب سخت است و اشکال‌زدایی (debug) آن ساده نخواهد بود!**
77+
.. note::
78+
پیاده‌سازی شیوه بازگشتی شاید به نظر هیجان‌انگیز باشد اما نباید فراموش کرد که میزان حافظه (Memory) زیادی مصرف می‌کند، اجرای آن زمان‌بر خواهد بود، درک جریان اجرای آن اغلب سخت است و اشکال‌زدایی (debug) آن ساده نخواهد بود!
79+
80+
81+
استفاده از decorator
82+
~~~~~~~~~~~~~~~~~~~~~
83+
84+
هنگام استفاده از decorator بر روی توابع بازگشتی باید به این نکته توجه داشته باشید که این decorator بر روی تمامی نمونه‌های فراخوانی شده از تابع اعمال خواهد شد و اینکه تنها یک نمونه از decorator ایجاد می‌شود و تمام نمونه‌‌های تابع به همان یک نمونه ارسال می‌شوند::
85+
86+
>>> def logger(func):
87+
... print('Decorator is created!')
88+
... def func_wrapper(number):
89+
... print(f'New factorial call with parameter: {number}')
90+
... result = func(number)
91+
... print (f'factorial({number}) ==> {result}')
92+
... return result
93+
... return func_wrapper
94+
...
95+
>>> @logger
96+
... def factorial(n):
97+
... if n <= 1:
98+
... return 1
99+
... else:
100+
... return n * factorial(n - 1)
101+
...
102+
>>>
103+
>>> factorial(5)
104+
Decorator is created!
105+
New factorial call with parameter: 5
106+
New factorial call with parameter: 4
107+
New factorial call with parameter: 3
108+
New factorial call with parameter: 2
109+
New factorial call with parameter: 1
110+
factorial(1) ==> 1
111+
factorial(2) ==> 2
112+
factorial(3) ==> 6
113+
factorial(4) ==> 24
114+
factorial(5) ==> 120
115+
120
116+
>>>
117+
118+
*به خروجی نمونه کد بالا حتما توجه نمایید!.*
78119

79120
تنظیم عمق بازگشتی
80121
~~~~~~~~~~~~~~~~~~~~
@@ -175,6 +216,71 @@
175216
[1, 2, 3, 4, 5, 5, 6, 7, 8, 9]
176217

177218

219+
Memoization
220+
~~~~~~~~~~~~~
221+
222+
**Memoization** یا یادآوری، یک تکنیک برای نگهداری از نتایج به دست آمده به منظور جلوگیری از تکرار محاسبات است [`ویکی‌پدیا <https://en.wikipedia.org/wiki/Memoization>`__]. این تکنیک را می‌توان در زبان برنامه‌نویسی پایتون با استفاده از **decorator** پیاده‌سازی کرد.
223+
224+
برای توضیح این بخش اجازه دهید یک مثال بازگشتی دیگر را بررسی کنیم. محاسبه مقدار فیبوناچی [`ویکی‌پدیا <https://en.wikipedia.org/wiki/Fibonacci_number>`__] یک عدد مشخص:
225+
226+
.. image:: /_static/l14-fibonacci-relation.png
227+
:align: center
228+
229+
::
230+
231+
>>> def fibonacci(n):
232+
... if n <= 1:
233+
... return n
234+
... else:
235+
... return fibonacci(n-1) + fibonacci(n-2)
236+
...
237+
>>> for number in range(10):
238+
... print(fibonacci(number))
239+
...
240+
0
241+
1
242+
1
243+
2
244+
3
245+
5
246+
8
247+
13
248+
21
249+
34
250+
251+
252+
در این مثال ما از عدد ``9`` جلوتر نرفتیم چرا که محاسبه برای اعداد بزرگتری به مانند ``50`` واقعا زمان‌بر خواهد بود و این فرصتی است تا ما کارایی تکنیک Memoization را محک بزنیم. اکنون تابع بازگشتی فیبوناچی خود را با استفاده از تکنیک Memoization و یک Decorator بهینه‌سازی می‌کنیم::
253+
254+
>>> def memoize_fibonacci(func):
255+
... memory = {}
256+
... def func_wrapper(number):
257+
... if number not in memory:
258+
... memory[number] = func(number)
259+
... return memory[number]
260+
... return func_wrapper
261+
...
262+
>>> @memoize_fibonacci
263+
... def fibonacci(n):
264+
... if n <= 1:
265+
... return n
266+
... else:
267+
... return fibonacci(n-1) + fibonacci(n-2)
268+
...
269+
>>>
270+
271+
حالا مقدار ``50`` که هیچ، مقدار فیبوناچی برای عدد ``500`` را محاسبه کنید (``(500)fibonacci``). تفاوت در زمان اجرا را خودتان متوجه خواهید شد!
272+
273+
274+
به کمک Decorator در این مثال (``memoize_fibonacci``) نتایج حاصل از فراخوانی هر نمونه تابع در جایی ذخیره می‌شود (شی دیکشنری ``memory``) و پیش از فراخوانی مجدد یک نمونه جدید از تابع بررسی می‌شود که آیا قبلا این مقدار محاسبه شده است یا خیر. در صورت وجود جواب از تکرار فراخوانی تابع صرف نظر و مقدار از پیش موجود به عنوان نتیجه برگردانده می‌شود. بنابراین بدیهی است که با جلوگیری از ایجاد نمونه توابع جدید و محاسبات تکراری، سرعت اجرا افزایش یابد.
275+
276+
277+
278+
279+
280+
281+
282+
283+
178284

179285

180286

0 commit comments

Comments
 (0)