Recursive vs. Iterative algorithms

Posted by teehoo on Stack Overflow See other posts from Stack Overflow or by teehoo
Published on 2010-04-14T22:10:17Z Indexed on 2010/04/14 22:13 UTC
Read the original article Hit count: 336

Filed under:

recursion

|

iteration

I'm implementing the Euclidian algorithm for finding the GCD (Greatest Common Divisor) of two integers.

Two sample implementations are given: Recursive and Iterative. http://en.wikipedia.org/wiki/Euclidean_algorithm#Implementations

My Question:

In school I remember my professors talking about recursive functions like they were all the rage, but I have one doubt. Compared to an iterative version don't recursive algorithms take up more stack space and therefore much more memory? Also, because calling a function requires uses some overhead for initialization, aren't recursive algorithms more slower than their iterative counterpart?

© Stack Overflow or respective owner

Related posts about recursion

tail recursion vs. forward recursion

as seen on Stack Overflow - Search for 'Stack Overflow'
Can someone give me the difference between these two kinds recursions and example? specifically in ocaml. Thanks >>> More
Are there advantages for using recursion over iteration - other than sometimes readability and elegance?

as seen on Programmers - Search for 'Programmers'
I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.). If it's true that recursion… >>> More
Python recursive function error: "maximum recursion depth exceeded"

as seen on Stack Overflow - Search for 'Stack Overflow'
I solved Problem 10 of Project Euler with the following code, which works through brute force: def isPrime(n): for x in range(2, int(n**0.5)+1): if n % x == 0: return False return True def primeList(n): primes = [] for i in range(2,n): if isPrime(i): … >>> More
Dynamic Programming Recursion and a sprinkle of Memoization

as seen on Stack Overflow - Search for 'Stack Overflow'
I have this massive array of ints from 0-4 in this triangle. I am trying to learn dynamic programming with Ruby and would like some assistance in calculating the number of paths in the triangle that meet three criterion: You must start at one of the zero points in the row with 70 elements. Your… >>> More
How does the recursion here work?

as seen on Stack Overflow - Search for 'Stack Overflow'
code 1: public static int fibonacci (int n){ if (n == 0 || n == 1) { return 1; } else { return fibonacci (n-1) + fibonacci (n-2); } } how can you use fibonacci if you haven't gotten done explaining what it is yet? I've been able to understand… >>> More

Related posts about iteration

Disco/MapReduce: Using results of previous iteration as input to new iteration

as seen on Stack Overflow - Search for 'Stack Overflow'
Currently am implementing PageRank on Disco. As an iterative algorithm, the results of one iteration are used as input to the next iteration. I have a large file which represents all the links, with each row representing a page and the values in the row representing the pages to which it links. For… >>> More
Iterative and Incremental Principle Series 4: Iteration Planning – (a.k.a What should I do today?)

as seen on Oracle Blogs - Search for 'Oracle Blogs'
Welcome back to the fourth of a five part series on applying the Iteration and Incremental principle. During the last segment, we discussed how the Implementation Plan includes the number of the iterations for a project, but not the specifics about what will occur during each iteration. … >>> More
The Product Owner

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
In a previous post, I outlined the rules of Scrum. This post details one of those rules. Picking a most important part of Scrum is difficult. All of the rules are required, but if there were one rule that is “more” required that every other rule, its having a good Product Owner. Simply put,… >>> More
AppKata - Enter the next level of programming exercises

as seen on Geeks with Blogs - Search for 'Geeks with Blogs'
Doing CodeKatas is all the rage lately. That´s great since widely accepted exercises are important to further the art. They provide a means of communication across platforms and allow to compare results which is part of any deliberate practice. But CodeKatas suffer from their size. They are intentionally… >>> More
Are there advantages for using recursion over iteration - other than sometimes readability and elegance?

as seen on Programmers - Search for 'Programmers'
I am about to make two assumptions. Please correct me if they're wrong: There isn't a recursive algorithm without an iterative equivalent. Iteration is always cheaper performance-wise than recursion (at least in general purpose languages such as Java, C++, Python etc.). If it's true that recursion… >>> More