Recursion and Iteration

Question

What is the difference? It is the same? If not, can someone please give an example?

MW: Iteration - 1: action or process of iteration or repetition: how: a procedure in which repeating a sequence of operations yields results sequentially closer to the desired result b: repeating a sequence of computer commands a certain number of times or until the condition is met

Recusion - 3: a computer programming method that involves the use of a procedure, subroutine, function or algorithm that calls itself one or more times until a specified condition is satisfied, during which the rest of each repetition is processed from the last one called to the first

Answer 1

We can distinguish (as is done in SICP) recursive and iterative procedures from recursive and iterative processes . First, as described in your definition, where recursion is basically the same as mathematical recursion : a recursive procedure is defined in terms of itself. An iterative procedure repeats a block of code using a loop statement. A recursive process, however, is one that accepts a non-constant (e.g., O (n) or O (lg (n)) space ) to execute, while an iterative process takes an O (1) (constant) space.

For mathematical examples, Fibonacci numbers are determined recursively:

Sigma designation is similar to iteration:

as the notation Pi . Just as some (mathematical) recursive formulas can be rewritten as iterative, some (but not all) recursive processes have iterative equivalents. All recursive procedures can be converted to iteratives by tracking partial results in your own data structure, rather than using a function call stack.

Answer 2

According to your definitions, these 2 are very different. There is no self-service in the iteration, but in recursion, the function calls itself

For instance. Iterative algorithm for factorial calculation

fact=1 For count=1 to n fact=fact*count end for 

And recursive version

 function factorial(n) if (n==1) return 1 else n=n*factorial(n-1) end if end function 

At all

Recursive code is shorter, but uses more memory. Sometimes recursion can be converted to iteration using dynamic programming.

Answer 3

[Hurry and exaggerate this!]

One form can be converted to another with one noticeable limitation: many "popular" languages ​​(C / Java / plain Python) do not support TCO / TCE (tail optimization / optimization / tail-call-elim), and thus, the use of recursion will "add extra data to the stack" every time a method calls itself recursively.

So, in C and Java, iteration is idiomatic, while in Scheme or Haskell, recursion is idiomatic.

Answer 4

Here's the Lisp function to find the length of the list. It is recursive:

 (defun recursive-list-length (L) "A recursive implementation of list-length." (if (null L) 0 (1+ (recursive-list-length (rest L))))) 

He reads: "the length of the list is 0 if this list is empty, or 1 plus the length of the sub-list, starting from the second element).

And this is strlen implementation - a C function that types the length of a char* string with nul-terminated. This is iterative:

 size_t strlen(const char *s) { size_t n; n = 0; while (*s++) n++; return(n); } 

The goal is to repeat some operation. Using iteration, you use an explicit loop (for example, while in strlen code). Using recursion, your function calls itself (usually) with a smaller argument, and so on, until the boundary condition is met ( null L in the code above). This also repeats the operation, but without an explicit loop.

Answer 5

Recursion: For example: Take, for example, a Fibonacci row. to get the fibonacci number, we need to know the previous one. So u will do the operation (same thing) for every number less than the given one, and each of these inturn calls the same method.

fib (5) = Fib (4) + 5

fib (4) = Fib (3) + 4,, reuse of the fib method

The iteration loops as if you added 1 + 1 + 1 + 1 + 1 (iterative addition) to get 5 or 3 * 3 * 3 * 3 * 3 (iterative multiplication) to get 3 ^ 5.

Answer 6

For a good example, consider recursive v. iterative procedures for depth search. This can be done using language functions using recursive function calls or in an iterative loop using a stack, but the process is essentially recursive.

Answer 7

For the difference between recursive and non-recursive; Recursive modes - a little easier to check for correctness; non-recursive implementation is more efficient .

Algorithms (4th Edition)