C++

Forum

 
Recursive function "slow" (sqrt)

donskanone (7)
Hey guys,

In order to learn working with recursive functions, I pogrammed a fcn that approximates the sqrt.

For sqrt(5,20) --> means calculate sqrt(5) in 20 iterations, everything works fine. But if I set sqrt(5,50) the program seems to crash (no response).

I wonder why that happens, as I heard that recursive functions are pretty efficient.

Thanks for inputs!

Cheers,
Sam

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#include <iostream>
#include <sstream>


using namespace std;

double sqrt(double s,int nums){
	if(nums == 0){
		return s/2;
	}
	else {
		return 0.5*(sqrt(s,nums-1)+s/sqrt(s,nums-1));
	}
}


int main(){
cout << sqrt(5,20) << endl;
return 0;
}
Chervil (7320)
You might consider how many times your function is called. At line 12
 
 
    return 0.5*(sqrt(s,nums-1)+s/sqrt(s,nums-1));
there are two calls to the function. Each of those will call the function two times each, and so on.


Consider this (effectively the same code with a count added):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
#include <iostream>
#include <sstream>
#include <iomanip>

using namespace std;
unsigned long long count = 0;

double sqrt(double s,int nums)
{
    ++count;
    if (nums == 0)
    {
        return s/2;
    }
    else 
    {
        return 0.5*(sqrt(s,nums-1) + s/sqrt(s,nums-1));
    }
}


int main()
{
    cout << setprecision(15) << fixed;
    for (int i=0; i<40; ++i)
    {
        count = 0;
        cout << setw(3) << i << "   ";
        cout << sqrt(5,i);
        cout << "  count = " << setw(10) << count << '\n';
    }
}

Output:
  0   2.500000000000000  count =          1
  1   2.250000000000000  count =          3
  2   2.236111111111111  count =          7
  3   2.236067977915804  count =         15
  4   2.236067977499790  count =         31
  5   2.236067977499790  count =         63
  6   2.236067977499790  count =        127
  7   2.236067977499790  count =        255
  8   2.236067977499790  count =        511
  9   2.236067977499790  count =       1023
 10   2.236067977499790  count =       2047
 11   2.236067977499790  count =       4095
 12   2.236067977499790  count =       8191
 13   2.236067977499790  count =      16383
 14   2.236067977499790  count =      32767
 15   2.236067977499790  count =      65535
 16   2.236067977499790  count =     131071
 17   2.236067977499790  count =     262143
 18   2.236067977499790  count =     524287
 19   2.236067977499790  count =    1048575
 20   2.236067977499790  count =    2097151
 21   2.236067977499790  count =    4194303
 22   2.236067977499790  count =    8388607
 23   2.236067977499790  count =   16777215
 24   2.236067977499790  count =   33554431
 25   2.236067977499790  count =   67108863
 26   2.236067977499790  count =  134217727
 27   2.236067977499790  count =  268435455
 28   2.236067977499790  count =  536870911
 29   2.236067977499790  count = 1073741823
 30   2.236067977499790  count = 2147483647
 31



Try replacing your line 12 with something like this:
1
2
 
        double root = sqrt(s, nums-1);
        return 0.5*(root + s/root);
donskanone (7)
Oh of course! Thanks for the good hint!! Works smooth now :-)
closed account (48bpfSEw)
You said: "recursive functions are pretty efficient"

This is a superstition... ^^

http://stackoverflow.com/questions/7703258/why-is-factorial-recursive-function-less-efficient-than-a-normal-factorial-funct




donskanone (7)
Well please apply correct citation :-) "I heard that .."

But of course, it matters how non-smart you implement it ;)
JLBorges (13770)
> recursive functions are pretty efficient.

Yes, tail call recursion is typically faster in functional programming languages (for instance Scheme) where operations on mutable objects are expensive.

In C++, the quality of implementation (tail-call optimisation) comes into play:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
#include <iostream>
#include <ctime>
#include <random>

struct timer
{
    ~timer()
    {
        const auto delta = std::clock() - start ;
        std::cout << delta * 1000.0 / CLOCKS_PER_SEC << " milliseconds.\n" ;
    };

    std::clock_t start = std::clock() ;
};

unsigned long long factorial_i( unsigned int n )
{
    unsigned long long result = 1 ;
    for( ; n > 1 ; --n ) result *= n ;
    return result ;
}

unsigned long long factorial_r( unsigned int n )
{ return n<2 ? 1 : n* factorial_r(n-1) ; }

int main()
{
    constexpr std::size_t SZ = 128'000'000 ;
    static unsigned int n[SZ] ;

    std::mt19937 rng ; // deliberately not seeded
    std::uniform_int_distribution< unsigned int > distr( 10, 19 ) ;
    for( auto& v : n ) v = distr(rng) ;

    int rv = 0 ;

    {
        std::cout << "iterative: " ;
        timer t ;
        for( auto v : n ) rv += factorial_i(v) % 2 ;
    }

    {
        std::cout << "recursive: " ;
        timer t ;
        for( auto v : n ) rv += factorial_r(v) % 2 ;
    }

    return rv > 0 ;
}


clang++ libc++ 3.8 x86_64 -O3
iterative: 3050 milliseconds.
recursive: 3010 milliseconds.

g++ libstdc++ 6.1 x86_64 -O3
iterative: 5390 milliseconds.
recursive: 5380 milliseconds.

http://coliru.stacked-crooked.com/a/13d49f357615aa57

Microsoft C++ 190023506 x86 -Ox (32-bit,smaller data set)
iterative: 4837 milliseconds.
recursive: 7447 milliseconds.

http://rextester.com/EKTS36777
closed account (48bpfSEw)
I am really surprised! Why can a tail-call-recursion-function be faster than the iterative one?!

... unless the factorial_r() at the tail is not really a function call... but this would mean that this is not really a recursion!

JLBorges (13770)
> ... unless the factorial_r() at the tail is not really a function call...

Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is not needed any more, and it can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call sequence is called tail call elimination. Tail call elimination allows procedure calls in tail position to be implemented as efficiently as goto statements ...
https://en.wikipedia.org/wiki/Tail_call


To make factorial_r tail-recursive, the compiler could rewrite it as:
1
2
3
4
5
6
7
8
9
 
unsigned long long factorial_r( unsigned int n )
// { return n<2 ? 1 : n* factorial_r(n-1) ; }
{ return factorial_r_rewritten( n, 1 ) ; }

unsigned long long factorial_r_rewritten( unsigned int n, unsigned long long result )
{ 
    if( n<2 ) return result ; 
    return factorial_r_rewritten( n-1, result*n ) ; // optimise: eliminate tail-call
}
closed account (48bpfSEw)
Thank you a lot for, JLBorges! Your explanations are very straight and clear to unterstand.

May I ask you in which projects you are involved with your qualifications?
JLBorges (13770)
> May I ask you in which projects you are involved with your qualifications?

I do not have a salaried job with one organisation; usually each week it is something different.

The majority of the projects deal with large scale software infrastructure. I do a fair amount of architecture, design and code reviews; in practise I spend a lot of tome teaching on the job.
Topic archived. No new replies allowed.