Recursion Vs Loop

[Omar El Gabry]

I came across many answers to this question and they all agreed on, loops have better performance than recursive function.

However, What i am trying to do here is showing me different result.

Kindly check the codes below, I am doing simple Operations using Array of size 10. But, what if i used an array with 10^5 size, I've tried it and the Recursive function was faster!

Hope to get a constructive answer :)

#include <cstdlib>
#include <iostream>
using namespace std;

 
int arr[10]={-1,1,1,2,3,4,5,6,7,8}; //the actual size of the array i've used was 10^5
/*
 This function is simply tries to find the indx in the array which has the same value ; arr[indx] = indx
 arr[0]=-1
 arr[1]=1 //indx of 1 has a value equlas to it's indx
 arr[2]=1
 arr[3]=2
 .
 .
 . 
 
 */
int getIndex(int indx){
 
    if(arr[indx] ==-1)
        return 0;
    if(arr[indx]==indx)
        return indx;
    return getIndex(arr[indx]);
}
int main() {
    int startIndex=9; //start indx
 
    cout<<getIndex(startIndex);
    return 0;
}

#include <cstdlib>
#include <iostream>
using namespace std;

 
int arr[10]={-1,1,1,2,3,4,5,6,7,8}; //the actual size of the array i've used was 10^5
/*
 This function is simply tries to find the indx in the array which has the same value ; arr[indx] = indx
 arr[0]=-1
 arr[1]=1 //indx of 1 has a value equlas to it's indx
 arr[2]=1
 arr[3]=2
 .
 .
 . 
 
 */
int getIndex(int indx){
 
    while(arr[indx]!=indx  && arr[indx]!=-1){
        indx=arr[indx];
    }
 
        return (arr[indx]==-1?0:indx); //if(arr[indx]==-1) return 0; else return indx;
}
int main() {
    int startIndex=9; //start indx
 
    cout<<getIndex(startIndex);
    return 0;
}
 

[Peter87]

Did you turn on compiler optimizations when you did your test? Did you use the same array in both tests? Did you load or generate the array in a way that made it impossible to compute the result at compile time?

[JLBorges]

> they all agreed on, loops have better performance than recursive function.
> However, What i am trying to do here is showing me different result.

Both clang++ and g++ consistently tend to generate slightly tighter code for the tail-recursive version of a simple function (TCO can be applied: exceptions, non-trivial destruction of local objects etc. are not involved).

clang++

ZN9recursive8getIndexEi:               # @_ZN9recursive8getIndexEi
.LBB0_1:                                # %tailrecurse
	movl	%edi, %ecx
	movslq	%ecx, %rax
	movl	arr(,%rax,4), %edi
	xorl	%eax, %eax
	cmpl	$-1, %edi
	je	.LBB0_3
	cmpl	%ecx, %edi
	movl	%ecx, %eax
	jne	.LBB0_1
.LBB0_3:
	ret

_ZN9iterative8getIndexEi:               # @_ZN9iterative8getIndexEi
.LBB1_1:                                # =>This Inner Loop Header: Depth=1
	movl	%edi, %eax
	movslq	%eax, %rcx
	movl	arr(,%rcx,4), %edi
	cmpl	$-1, %edi
	je	.LBB1_3
	cmpl	%eax, %edi
	jne	.LBB1_1
.LBB1_3:
	xorl	%ecx, %ecx
	cmpl	$-1, %edi
	cmovel	%ecx, %eax
	ret

g++

_ZN9recursive8getIndexEi:
.L3:
	movslq	%edi, %rax
	movl	arr(,%rax,4), %edx
	cmpl	$-1, %edx
	je	.L4
	cmpl	%edx, %edi
	je	.L5
	movl	%edx, %edi
	jmp	.L3
.L4:
	xorl	%eax, %eax
	ret
.L5:
	movl	%edi, %eax
	ret

_ZN9iterative8getIndexEi:
.L11:
	movslq	%edi, %rax
	movl	arr(,%rax,4), %edx
	cmpl	%edi, %edx
	je	.L8
	cmpl	$-1, %edx
	je	.L12
	movl	%edx, %edi
	jmp	.L11
.L8:
	cmpl	$-1, %edi
	je	.L12
	movl	%edi, %eax
	ret
.L12:
	xorl	%eax, %eax
	ret

Excerpted from: http://coliru.stacked-crooked.com/a/3d5c10b30a54f9f3

[Duthomhas]

What these responses are saying is that the performance (and space) hit you get from recursion is from the overhead of calling a function, which, while small, is still significant. However, a function that is properly tail-call recursive (meaning that the only thing that changes are the function arguments and no further computation needs be done after the recursion*) then the compiler can silently insert a loop in your code.

*plus some other technical stuff that may vary

[JLBorges]

The question was: what if i used an array with 10^5 size, I've tried it and the Recursive function was faster!

What the response is saying is: with clang++ and g++, the code generated by these compilers for the recursive version (where TCO can be applied) tends to be a wee bit faster than that for the equivalent iterative version.

[Duthomhas]

There was more than one question, dude. You all answered the second. I answered the first. So stop hating.