##### Why recursive function consumes more of processing time than loops?
 Why recursive function consumes more of processing time than loops? M83Linux Programmer named Tim Posts: 6 Threads: 2 Joined: Jul 2020 Reputation: May-11-2021, 11:42 PM (This post was last modified: May-11-2021, 11:43 PM by M83Linux.) Hi All, Why recursive function consumes more processing time than loops? And, Is it cumbersome for the processor? ```def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) print fibonacci(40)```^^^^ this example takes about 1 min, but with loop only few ms Reply bowlofred Da Bishop Posts: 1,156 Threads: 3 Joined: Mar 2020 Reputation: May-11-2021, 11:50 PM I assume your loop is not written identically. Recursion means a function call. A function call will take more time and memory than just executing a loop. But the difference isn't huge. But your program is written in a way where you're redoing your work over and over and over. I'm assuming your loop was not written that way. The slowness is due to the algorithm, not inherently the recursion. If you add a memoization cache to it, it will complete quickly. ```from functools import lru_cache @lru_cache def fibonacci(n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(40))``` M83Linux likes this post Reply M83Linux Programmer named Tim Posts: 6 Threads: 2 Joined: Jul 2020 Reputation: May-12-2021, 12:52 AM (May-11-2021, 11:50 PM)bowlofred Wrote: If you add a memoization cache to it, it will complete quickly. Thank You alot (May-11-2021, 11:50 PM)bowlofred Wrote: `from functools import lru_cache` i can't import that coz i'm using v2.7 Reply bowlofred Da Bishop Posts: 1,156 Threads: 3 Joined: Mar 2020 Reputation: May-12-2021, 01:09 AM Python 2 is very old and there's lots of things that no longer support it. You should figure out what is preventing you from using python 3 and try to address it. M83Linux likes this post Reply deanhystad So-and-so of the Yard Posts: 2,013 Threads: 11 Joined: Feb 2020 Reputation: May-12-2021, 03:06 AM (This post was last modified: May-17-2021, 06:31 PM by deanhystad.) I ran this code ```def fib(n): fib.count += 1 if n < 2: return 1 else: return fib(n-2) + fib(n-1) fib.count = 0 print(fib(40)) print(fib.count)```The fib function was called 331,160,281 times Then I ran this code that uses a dictionary to save and reuse partial results: ```def fib(n): fib.count += 1 a = partial_results.get(n, None) if a is None: a = fib(n-2) + fib(n-1) partial_results[n] = a return a partial_results = {0:0, 1:1} fib.count = 0 print(fib(40)) print(fib.count)```This is similar to what Python does for you using the cache, but expanded out so you can see the mechanism. The result was the same, but the fib function is only called 79 times. If I were to compute multiple Fibonacci numbers many of them could be calculated by a single call to fib. So raw recursion takes longer because it is doing a ridiculous number of function calls calculating the same results over and over and over. M83Linux and ibreeden like this post Reply M83Linux Programmer named Tim Posts: 6 Threads: 2 Joined: Jul 2020 Reputation: May-17-2021, 05:47 PM (May-12-2021, 03:06 AM)deanhystad Wrote: The fib function was called 331,160,281 times I'm shocked. trying to understand from where this huge number come! Reply deanhystad So-and-so of the Yard Posts: 2,013 Threads: 11 Joined: Feb 2020 Reputation: May-17-2021, 06:29 PM (This post was last modified: May-17-2021, 06:29 PM by deanhystad.) Starting with a really simple case: fib[4] = fib[3] + fib[2] fib[4] = (fib[3] = fib[2] + fib[1]) + (fib[2] = fib[1] + fib[0]) fib[4] = (fib[3] = (fib[2] = fib[1] + fib[0]) + fib[1]) + (fib[2] = fib[1] + fib[0]) That's 9 calls to fib(). This code records the number of times fib[n] is called for each value of n: ```calls = {} def fib(n): calls[n] = calls.get(n, 0) + 1 if n < 2: return 1 else: return fib(n-1) + fib(n-2) fib(5) for n, count in calls.items(): print(f'{n:3d} : {count:5d}') print('Total', sum(calls.values()))`````````Output: 5 : 1 4 : 1 3 : 2 2 : 3 1 : 5 0 : 3 Total 15``````Just doubling starting n from 5 to 10 does this: ``````Output:10 : 1 9 : 1 8 : 2 7 : 3 6 : 5 5 : 8 4 : 13 3 : 21 2 : 34 1 : 55 0 : 34 Total 177``````And this is the horrible thing that happens when n = 40 ``````Output: 40 : 1 39 : 1 38 : 2 37 : 3 36 : 5 35 : 8 34 : 13 33 : 21 32 : 34 31 : 55 30 : 89 29 : 144 28 : 233 27 : 377 26 : 610 25 : 987 24 : 1597 23 : 2584 22 : 4181 21 : 6765 20 : 10946 19 : 17711 18 : 28657 17 : 46368 16 : 75025 15 : 121393 14 : 196418 13 : 317811 12 : 514229 11 : 832040 10 : 1346269 9 : 2178309 8 : 3524578 7 : 5702887 6 : 9227465 5 : 14930352 4 : 24157817 3 : 39088169 2 : 63245986 1 : 102334155 0 : 63245986 Total 331160281`````` ibreeden and M83Linux like this post Reply M83Linux Programmer named Tim Posts: 6 Threads: 2 Joined: Jul 2020 Reputation: May-17-2021, 06:58 PM (May-17-2021, 06:29 PM)deanhystad Wrote: Starting with a really simple case: that makes sense now, i benefited a lot from you thank you Reply csr Unladen Swallow Posts: 4 Threads: 0 Joined: May 2021 Reputation: May-20-2021, 12:31 PM This is why using recursion shouldn't be taken for granted. The use of resources can easily become exponential; and the more resources are used per function call, the worse it'll be. While recursion can provide a simpler and more readable solution to a problem, you'll be able to achieve similar results if you use the right tools. For instance, this code: ```def fib(n): fibs = [] for i in range(n + 1): if i < 2: fibs.append(i) else: fibs.append(fibs[i - 2] + fibs[i - 1]) return fibs[-1] if n >= 0 else 0```Provides the same simple solution by making use of a list to save and use the results as we iterate from 0 to n (included). The memory footprint in this case is minimal (only one function call and a list), as we don't take additional steps to keep track of n-1 and n-2 in order to calculate and use these. Reply DeaD_EyE Da Bishop Posts: 1,623 Threads: 6 Joined: May 2017 Reputation: May-20-2021, 01:52 PM Quote:Why recursive function consumes more of processing time than loops? Calling a function takes time and requires also resources. Iterating over something is faster than calling. A call of a function is for a human very short, but if you do this one million times, you can recognize the difference. My code examples are always for Python >=3.6.0 Almost dead, but too lazy to die: https://sourceserver.info All humans together. We don't need politicians! Reply

 Possibly Related Threads… Thread Author Replies Views Last Post Real Time Audio Processing with Python Sound-Device not working Slartybartfast 2 632 Mar-14-2021, 07:20 PM Last Post: Slartybartfast Combine Two Recursive Functions To Create One Recursive Selection Sort Function Jeremy7 12 1,149 Jan-17-2021, 03:02 AM Last Post: Jeremy7 Can you end the Time.sleep function boier96 9 694 Jan-16-2021, 10:09 PM Last Post: Serafim Real Time signal processing tagalog 2 567 Dec-12-2020, 05:23 AM Last Post: tagalog Execution of Another Recursive Function muzikman 5 573 Dec-04-2020, 08:13 PM Last Post: snippsat Don't Understand Recursive Function muzikman 9 691 Dec-03-2020, 05:10 PM Last Post: muzikman list call problem in generator function using iteration and recursive calls postta 1 387 Oct-24-2020, 09:33 PM Last Post: bowlofred function call at defined system time? Holon 5 804 Oct-06-2020, 03:58 PM Last Post: snippsat Real-time processing tagalog 5 932 Oct-06-2020, 03:45 PM Last Post: tagalog Recursive function returns None, when True is expected akar 0 768 Sep-07-2020, 07:58 PM Last Post: akar

Forum Jump:

### User Panel Messages

##### Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020