CODEWITHSUNDEEP
recursioniteration
None
None

Reputation: 602

a recursive algorithm converted to single loop becomes iterative/linear?

i've successfully written a typical algorithm to solve a maze recursively. then restructured the same algorithm into a single 'while' loop.

both methods implement an ArrayList that more or less behaves like a stack. (i'd be happy to post the code for both scenarios or a git repo if needed)

the first method is obviously by definition/design recursive. and they both achieve the same goal successfully with the only difference being that the recursive method is much more resource intensive, and limits the size/complexity of the required solution by available memory allocation.

my question is.., by restructuring 'recursion' into a single 'loop' now classify the algorithm as 'iterative/linear' by default?

Upvotes: 1

Views: 54

Answers (1)

Luca T
Luca T

Reputation: 668

I would call it iterative -- as it iterates over a loop -- but not necessarily linear, as that would imply that your iterative algorithm has an execution time that scales linearly with your input (for example, the number of crossroads) which may or may not be the case.

In general, the term linear associated with algorithms is usually referred to as an indication of its time complexity being -- you guessed it -- linear (e.g. scales linearly with a certain parameter, usually its inputs). The term iterative, on the other hand, just refers to its implementation using iterative syntactical structures (usually loops) and is often used as an antonym of recursive.

It is important to note that certain types of recursion can perform as well as their iterative counterpart (e.g tail recursions), so that compilers can automatically convert them to loops.

Upvotes: 2

Related Questions