0

Are there algorithms that are only feasible in a recursive manner? If yes, how can one identify these algorithms?

Consider the following as a case study.

In order to approximate a exponential, one can use.

ef ≈ 1 + f(1 + f/2(1 + f/3(1 + f/4)))

Here is a function that computes this approximation at a level of n steps using recursion.

exp_approximation = function(f, n, i = 2)
{
    if (n == 1)
    {
        return( 1 + f/i )
    } else
    {
        1 + f/i * exp_approximation(f,n=n-1,i=i+1)
    }

}

Is it possible to write the same algorithm using iteration instead of recursion?

I wrote my code in R but I welcome solution in pseudo code other some other commonly used language such as C, C++, Java, Python, ...

Remi.b
  • 17,389
  • 28
  • 87
  • 168
  • Well, recursiveness does improve time complexity of its non-recursive version. So one straightforward answer would be "Algorithms with *really* high time complexity may only be feasible with a recursive approach" – DarkCygnus Jul 04 '17 at 17:37
  • 1
    @GrayCygnus How exactly it improves the complexity? – SomeWittyUsername Jul 04 '17 at 17:51

1 Answers1

0

Yes, technically it's possible. See, for example, this question for a generic conversion method. That said, many algorithms are much more intuitive in the recursive form (and might be more efficient in functional languages but not in imperative ones). That's especially true for math-related problems involving recurrences, where recursion is in fact a representation of a recurrence relation.

SomeWittyUsername
  • 18,025
  • 3
  • 42
  • 85
  • Basically no CPUs have function support so the compilers fake it by making a stack data structure to handle arguments. Its no different than the "conversion" so as a process it still is recursive. – Sylwester Jul 04 '17 at 18:54
  • @Sylwester Not sure what you mean by "no CPUs have function support". And of course the functionality is the same, otherwise the implementation wouldn't be equivalent. – SomeWittyUsername Jul 04 '17 at 21:12
  • The x86 `call` instruction calls a subroutine until it returns with `ret`. No arguments so its not function support. Arguments has to be provided by means of an external data structure by the compiler/interpreter. Many uses the same data structure as the `call` uses and thus needs to massage it so that `ret` works. eg. extra code before and after `call` and before `ret` does the magic and not the CPU itself. So if recursive functions on machine level really doesn't exist would manually translating code to not use a compiler feature make it iterative when the result is the same? – Sylwester Jul 05 '17 at 11:33
  • @Sylwester Normally recursion is defined on an algorithm/SW level. When diving down into the implementation (such as asm/binary form or HW) this may well change (and probably will at some point) but it doesn't contradict the fact that the input program was recursive. – SomeWittyUsername Jul 05 '17 at 13:00
  • In Scheme, which requires TCO tail recursion is often called iterative process. Only when the stack grows its called a recursive process. Scheme doesn't have other looping constructs than recursion, but it has library syntax for loops that becomes iterative recursion. The only reason to want to translate between recursion and iteration is because the resulting code leaks limitations like too little stack space. It never have anything to do with algorithm/sw level. – Sylwester Jul 17 '17 at 21:28
  • Sylwester@ Scheme internal restrictions and recursion implementation do not and can not project of **what is** recursion (which is a pure algorithmic construct in it's most general form). It's the other way around. Recursion is natural for functional languages such as Scheme and probably performs better than iteration (which is more natural to imperative languages). And I never said that **direct** translation from recursive to iterative implementation is a good idea, however it's feasible. Anyway, regarding the efficiency - that's a correct comment, I'll add clarification. – SomeWittyUsername Jul 18 '17 at 11:05