When Is Recursion Useful?

Question

I am relatively new to python and have recently learned about recursion. When tasked to find the factorial of a number, I used this:

def factorial(n):
    product = 1
    for z in xrange(1,n+1):
        product *= z
    return product

if __name__ == "__main__":
    n = int(raw_input().strip())
    result = factorial(n)
    print result

Then, because the task was to use recursion, I created a solution that used recursion:

def factorial(n):
    if n == 1:
        current = 1
    else:
        current = n*(factorial(n-1))  
    return current

if __name__ == "__main__":
    n = int(raw_input().strip())
    result = factorial(n)
    print result

Both seem to produce the same result. My question is why would I ever use recursion, if I could use a for loop instead? Are there situations where I cannot just create for loops instead of using recursion?

All recursion can be refactored to use looping and other such constructs. Recursion can be *easier to read and understand* sometimes. — Martijn Pieters, Oct 27 '17 at 15:37
Recursion is great for things like navigating tree data structures. How do you navigate a tree? Start at the root, navigate the left child of the tree, navigate the right child of the tree. How do you navigate the children? *The exact same way you navigate the root.* So it's convenient to use recursion here. The stack keeps track of where you are in the tree; you don't have to keep track of that explicitly. When you come up with a recursive solution to a problem that's suited to being solved that way, it's almost like magic. "Is that all there is?" Yes, it is. — kindall, Oct 27 '17 at 15:40
maybe this question can help you https://stackoverflow.com/questions/72209/recursion-or-iteration — Cyberguille, Oct 27 '17 at 15:43
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation. [on topic](http://stackoverflow.com/help/on-topic) and [how to ask](http://stackoverflow.com/help/how-to-ask) apply here. There are many discussions of this on line ... — Prune, Oct 27 '17 at 16:22

Cyberguille · Answer 1 · 2017-10-27T16:34:05.380

For every solution that you found with recursion there are a solution iterative, because you can for example simulate the recursion using an stack.

The example of Factorial use a type of recursion named Tail Recursion an this cases have an easy way to implement iterative, but in this case recursion solution is more similar to the mathematical definition. However there are other problems that found an iterative solution is difficult and is more powerful and more expressive use recursive solution. For example the problem of Tower of Hanoi see this question for more informationTower of Hanoi: Recursive Algorithm, the solution of this problem iterative is very tedious and finally have to simulate a recursion.

There are problems like Fibonacci sequence that the definition is recursive an is easy to generate a solution recursive

def fibonacci(n):
    if ((n==1) or (n==2)):
        return 1
    else (n>2):
        return fibonacci(n-2) + fibonacci(n-1)

This solution is straight forward, but calculate many times unnecessarily the fibonacci of n-2 see the image bellow to better understanding the fibonacci(7)

So you can see the recursion like syntactic sugar some time, but depends of what you want, you need to decide if use or no. When you program in Low-level programming language the recursion is not used, when you program a microprocessor is a big error, but on others case is better use a recursive solutions for better understanding of your code.

hope this help, but you need go deep reading books.

When Is Recursion Useful?

1 Answers1