Converting to tail recursive algorithm

closed account (4ET0pfjN)
Hi, here is my simple linear recursive algorithm to sum elems of an array. Does anyone know how I can convert this to be optimized, to be tail recursive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int r_linear_sumArray_v1(int* list, int size, int start)
{
   if ( start == (size - 1) )
      return list[start];
   else
      return r_linear_sumArray_v1(list, size, start + 1) + list[start];//when base case reached, that elem is added to the current index start just after the popped base case
}

int main()
{
   int quickList[] = {100,20,3009,4};
   int qSize = sizeof(quickList)/sizeof(int);   

   int sum = r_linear_sumArray_v1(&quickList[0], qSize, 0);  
   return 0;
}
This is one way to get a tail-recursive form:
1
2
3
4
5
int sum( const int* array, std::size_t size, std::size_t start, int sum_so_far = 0 )
{
    if( size == start ) return sum_so_far ;
    return sum( array, size, start+1, sum_so_far + array[start] ) ;
}


Iterative code generated by g++ 4.8 x86 with -fomit-frame-pointer -O3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
__Z3sumPKijji:
	pushl	%ebx
	movl	12(%esp), %ecx
	movl	16(%esp), %edx
	movl	8(%esp), %ebx
	movl	20(%esp), %eax
	cmpl	%edx, %ecx
	je	L2
	leal	(%ebx,%edx,4), %edx
	leal	(%ebx,%ecx,4), %ecx

L3:
	addl	(%edx), %eax
	addl	$4, %edx
	cmpl	%ecx, %edx
	jne	L3

L2:
	popl	%ebx
	ret

Topic archived. No new replies allowed.