Are recursive functions faster than iteration?

1

Are recursive functions faster than iteration??
Thanks And Regards
Krishna Wadhwani

1 Like
2

I m not the right guy to answer…but upto my knowledge both have its own advantage…sometimes recursive hlps more instead of iterative or sometimes iterative :slightly_smiling_face:@vijju @ssjgz helps more.

4

it’s complicated.

2 Likes
5

I would like to share my knowledge on this.
Functions are stored in some memory called stack frame. The size of the stack increases with the increase in recursion depth. Also, when a base case is reached, control is returned to the calling function. The return statement is very costly because it results in control being transferred from one memory location to another, it adds some overhead in execution time.
A simple program that illustrates the execution times of a program doing the same activity iteratively vs recursively.

// Recursion
#include <stdio.h>

int gcd(int a, int b) {
    if (a == 0)
        return b;
    return gcd(b%a, a);
}

int main() {
    int tests = 10000000;
    int a = 10000000;
    int b = 1000;
    for(int i = 0; i < tests; i++) {
        printf("%d\n", gcd(a, b));
        a--;
        b++;
    }
    return 0;
}

suman@skynet:~$ time ./gcd1 > out.out

real	0m1.960s
user	0m1.829s
sys	    0m0.032s
suman@skynet:~$ time ./gcd1 > out.out

real	0m1.968s
user	0m1.853s
sys	    0m0.012s

// Iteration
#include <stdio.h>

int gcd(int a, int b) {
    for(int rem; b > 0; rem = a % b, a = b, b = rem);
    return a;
}

int main() {
    int tests = 10000000;
    int a = 10000000;
    int b = 1000;
    for(int i = 0; i < tests; i++) {
        printf("%d\n", gcd(a, b));
        a--;
        b++;
    }
    return 0;
}

suman@skynet:~$ time ./gcd2 > out.out 

real	0m1.932s
user	0m1.830s
sys	    0m0.000s
suman@skynet:~$ time ./gcd2 > out.out 

real	0m1.859s
user	0m1.829s
sys	    0m0.004s

As you can see, iteration is a bit faster than recursion, although I am unable to show a significant difference between the execution times.
You can try the same with other algorithms like binary search (can be implemented iteratively as well as recursively) to find which is faster.
And as mentioned by @ssjgz , it is not the same with all languages. Recursion is faster in some languages.

1 Like
6

Once requirement can’t answer everything, better to test your code with both and then submit the one which is faster.

7

Thanks @player_06 @nichke @ssjgz @suman_18733097 @rds_98 To Answer My Question

5 Likes
8

No need to thank me, my answer was obviously incorrect, so don’t take it into consideration please. That’s why I deleted it in the first place. But others gave some interesting insights and I have to thank to y’all as well.

9

@suman_18733097 Like Which Languages??

1 Like
10

@nichke No, Atleast You Spent Time On My Question :slight_smile:

2 Likes
11

Yeah , recursive function is faster than iterative ones…but recursive has own advantages
and iterative has own…

12

The whole Stack overflow answer:

This depends on the language being used. You wrote ‘language-agnostic’, so I’ll give some examples.

In Java, C, and Python, recursion is fairly expensive compared to iteration (in general) because it requires the allocation of a new stack frame. In some C compilers, one can use a compiler flag to eliminate this overhead, which transforms certain types of recursion (actually, certain types of tail calls) into jumps instead of function calls.

In functional programming language implementations, sometimes, iteration can be very expensive and recursion can be very cheap. In many, recursion is transformed into a simple jump, but changing the loop variable (which is mutable) sometimes requires some relatively heavy operations, especially on implementations which support multiple threads of execution. Mutation is expensive in some of these environments because of the interaction between the mutator and the garbage collector, if both might be running at the same time.

I know that in some Scheme implementations, recursion will generally be faster than looping.

In short, the answer depends on the code and the implementation. Use whatever style you prefer. If you’re using a functional language, recursion might be faster. If you’re using an imperative language, iteration is probably faster. In some environments, both methods will result in the same assembly being generated (put that in your pipe and smoke it).

Addendum: In some environments, the best alternative is neither recursion nor iteration but instead higher order functions. These include “map”, “filter”, and “reduce” (which is also called “fold”). Not only are these the preferred style, not only are they often cleaner, but in some environments these functions are the first (or only) to get a boost from automatic parallelization — so they can be significantly faster than either iteration or recursion. Data Parallel Haskell is an example of such an environment.

List comprehensions are another alternative, but these are usually just syntactic sugar for iteration, recursion, or higher order functions.

13

But Why Recursive Are Faster @avx_5801 BTW Thanks For Answer

1 Like
14

Not always…

15

Thanks @suman_18733097

2 Likes
16

What Is The Main Difference Between Iterative And Recursive Approach

1 Like
17

You can find it on Geeksforgeeks

18

Hurray Now I Am 2 :star2: Coder

1 Like
19

Thanks @suman_18733097

1 Like
20

Is Java Faster In Recursive Approach Or Iterative Approach

package com.learningjava;

public class Practice_Set_On_Method {
    //Recursive Approach
    static void table_recursive(int n, int i){
        if (i > 10){
            return ;
        }
        System.out.println(n+" * "+i+" = "+n*i);
        table_recursive(n, i+1);
    }
    //Iterative Approach
    static void table_iterative(int n){
        for (int i = 1; i <= 10; i++){
            System.out.println(n*i);
        }
    }
    public static void main(String[] args) {
        //Problem 1
        //Write A Program To Write Multiplication Tables
        //Ans
        //Recursive
        System.out.println("Recursive");
        table_recursive(3, 1);
        //Iterative
        System.out.println("Iterative");
        table_iterative(3);
    }
}

Which Will Run Faster??

1 Like
21

Which Will Run Faster??

1 Like