CODEWITHSUNDEEP
pythonrecursionwhile-loop
Ahmad Muhammad
Ahmad Muhammad

Reputation: 1

Looping or Recursion

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.

Upvotes: 0

Views: 54

Answers (1)

TheBrownCoder
TheBrownCoder

Reputation: 1226

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

  1. The implementation of the recursive solutions is much simpler than the iterative solution
  2. 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

Upvotes: 1

Related Questions