Looping or Recursion

Question

I wrote two programs to calculate the factorial of a number. 1:

import time
x  = int(input('>'))

t1 = time.time()
fact=1
if x==0:
    print('undefined')
elif x==1:
    print(1)
else:
    while x!=1:
        fact *= x
        x -= 1
    print(fact)      
print(time.time()-t1)

2:

import time

def fact(n):
    if n==0:
        return 'undefined'
    elif n==1:
        return 1
    else:
        return n*fact(n-1)


x = int(input('>'))
t1 = time.time()
print(fact(x))
t = time.time()-t1
print(t)

The average runtime of the second program was less than the first one. Now my question is which one is really better than the other and what else we use method 2 for (don't want any code examples). And I'm sorry if the question was asked before (which it probably was), I searched for a while but was not able to find it.

Both run on O(n) for runtime complexity. The recursion has a bigger memory complexity: O(n^2), though. A lot of compilers turn recursion into iteration without you knowing and that’s one of the reasons. — regina_fallangi, Aug 12 '18 at 06:13
By better I mean which is more efficient in terms of memory and processing power. — Ahmad Muhammad, Aug 12 '18 at 06:18
When you get the slowest one to compute for a minute, how long time did the fastest one take? — Sylwester, Aug 12 '18 at 11:44
Well the method 2 is limited to 996 recursive depth, so i ran 6 tests each for calculation of 996! Method 1. Took an average of 0.03 s whereas method 2. Took 0.023s but it is limited method 1 can go quite far until I guess we get an integer overflow. — Ahmad Muhammad, Aug 12 '18 at 12:32

TheBrownCoder · Answer 1 · 2018-08-12T06:37:36.703

Better is naturally a subjective term. As mentioned in the comments, both run in O(n) time in terms of runtime complexity. However, depending on the details of the language, recursive functions often take up more space in memory.

Specifically, since you seem to be using Python, each recursive call requires a new function call frame, keeping track of that function call's variables. This takes up significantly more space than a simple loop while taking effectively the same amount of time. In fact, to limit your use of deep recursion, Python by default has a recursion depth limit of 1000; aka, you would not be able to calculate the factorial of numbers above 1000 this way.

Generally speaking, which is the better option depends on the language. And loops will almost always take up less if not equal space to a recursive function. However, this doesn't mean that recursion is useless! When it comes to a simple example like the factorial function, recursion is not at all necessary. However when you are building complex data structures or algorithms, recursion is occasionally necessary if not incredibly cleaner in order to write your solution.

Ultimately Recursion and Loops are nearly the same. I prefer to use recursion when

The implementation of the recursive solutions is much simpler than the iterative solution
I can be sure that the recursion won't cause a stack overflow by going too deep into the callstack

Tree Traversal, Graph Traversal, and Sorting are all good examples of places that recursion is likely your best option

Right so it depends on what I am trying to do one will perform better in certain situations and the other won't. — Ahmad Muhammad, Aug 12 '18 at 06:27
The thing is, looping and recursion are effectively the same thing. A general rule of thumb is to prefer recursion when 1) it makes the code much simpler and easier to write and 2) you can be sure it won't cause a stack overflow by going too deep — TheBrownCoder, Aug 12 '18 at 06:36
Different languages optimize recursion as well. You could look into https://stackoverflow.com/questions/33923/what-is-tail-recursion?rq=1 if you're interested — TheBrownCoder, Aug 12 '18 at 06:38
There is also the fact that every recursion canbe turned into iteration and viceversa. I advocate for recursion in cases of dynamic programming, for cleaner code. But in real case scenarios, it’s hard to use recursion without (unnecessarily) harminf your memory. — regina_fallangi, Aug 12 '18 at 06:51

Looping or Recursion

1 Answers1