Some of the problems we must solve in computer science rely on the solutions that come from solving smaller parts of the bigger problem. In this discussion define recursive algorithms, and with the use of code examples, demonstrate whether it is possible to convert a recursive algorithm into an iterative algorithm.

 

Answer:

What is a Recursive algorithm?

We will call recursive algorithms to those who make recursive calls to reach the result,  and iterative algorithms to those who arrive at a result through iteration through a defined or indefinite cycle.

Any recursive algorithm can be expressed as iterative and vice versa. However, depending on the conditions of the problem to be solved it may be preferable to use the recursive solution or the iterative.

Recursive algorithms are based on the methodology of repeatedly calling the function in which they are defined, and are very useful in many fields in computing.

Example:

def factorial(n):

   """ Precondition: n whole >=0

       Bring back: n! """

   fact = 1

   for num in xrange(n, 1, -1):

       fact *= num

   return fact

General recursion can often be replaced by queue recursion by collecting partial results in an accumulator and transmitting it with the recursive call. The recurrence of the queue is essentially iterative, the recursive call can be implemented as a hop.

For example, the standard general recursive definition of factorial

 factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

can be replaced by

 factorial(n) = f_iter(n, 1)

And

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

which is recursive tail It's the same as

 a = 1; while (n$ = 0) × a = n * a; n = n - 1; } return a;

Check out these links for performance examples

Vs Iteration (Looping): Speed and memory comparison

And

Replace recursion with iteration

And

Recursion vs iteration

Q: Is the recursive version usually faster? A: No, it is usually slower (due to the overhead of maintaining the stack)

Q: Does the recursive version usually use less memory?

A: No -- it usually uses more memory (for the stack).

Q: Then why use recursion??

A: Sometimes it is much simpler to write the recursive version (but I usually start from the base case (each recursive function has one) and work backwards, storing the results in a cache (array or hashtable) if necessary.

Its recursive function solves an issue by resolving smaller subproblems and using them to solve the largest instance of the problem. Each sub-problem is also broken down further and further until the subproblem is so small that the solution is trivial (i.e. the base case).

The idea is to start in the base case (or base cases) and use it to build the solution for larger cases, and then use them to build even larger cases, and so on, until the whole problem is solved. This does not require a stack, and can be done with loops.

A simple example (in Python):

 #recursive version def fib(n): if n==0 or n==1: return n else: return fib(n-1)+fib(n-2) #iterative version def fib2(n): if n==0 or n==1: return n prev1,prev2=0,1 # start from the base case for i in xrange(n): cur=prev1+prev2 #build the solution for the next case using the previous solutions prev1,prev2=cur,prev1 return cur

Itis possible to convert a recursive algorithm into an iterative algorithm.

All recursive algorithms can be implemented  iteratively, "emulating" recursion with an explicit LIFO data structure. But that does not change the algorithm itself,  i.e. the algorithm remains recursive, not iterative.

Meanwhile, recoil is an inherent property of recursion. If you have recoil, you have recursion. As you probably know, a class of algorithms that allows a genuine and direct conversion to iteration are the recursive queue algorithms. But the presence of recoil immediately means that its recursion is not a tail recursion.

What you can do is try to invent an algorithm that doesn't require going back. That, of course, will be a completely different algorithm, not a conversion of the original recursive algorithm to an iterative form.

recursive algorithms can be converted into iterative algorithms and vice versa. This is a direct result of Church-Turing's thesis.

It may not always be obvious (or trivial), but any algorithm can be expressed as a recursive or iterative process; for the general case, this question has been answered above.

As for how, there are several techniques that can be applied to move from one style to another, for example, take a look at this answer, or for a more detailed discussion read this article that explains how to use stacks to eliminate recursion.