-2

I'm trying to simulate functional programming in c++ , I'm stucking on "wait" function , assume I want to wait for 100 seconds without using any kind of loops , just recursion . How can I avoid Stack Overflow ?

Mostafa 36a2
  • 157
  • 1
  • 15
  • Why would you want a wait function that uses all of the CPU possible instead of using `std::this_thread::sleep_(for|until)`? – chris Jan 01 '14 at 13:38
  • sleep() doesn't help you? – Digital_Reality Jan 01 '14 at 13:40
  • wait function is an example , what if I want to wait for some key to press , I know Sleep function , but i'm trying to do it , functionally . thanks – Mostafa 36a2 Jan 01 '14 at 13:40
  • Unless you use some library function there is no guarantee that your process will wait for specified time say 100 sec here!! – Digital_Reality Jan 01 '14 at 13:42
  • @Mostafa36a2, Then there are methods specifically suited for waiting for keypresses that don't hog the CPU, like a message loop for a window or a keyboard hook. Going for functional programming, it would be better to focus on tasks where it doesn't hinder the program unnecessarily. – chris Jan 01 '14 at 13:46
  • You can't simulate a functional `wait`. `wait` exists solely for it's side-effects, therefore a functional `wait` makes no sense. – Idan Arye Jan 01 '14 at 14:27
  • @IdanArye The question is about functional programming, not **pure** functional programming. And, in fact, with suitable wrappers, there are models of I/O that fit very well into the pure functional paradigm. Go look up Monadic IO. – Pitarou Jan 01 '14 at 15:29

3 Answers3

2

Make the calls tail-recursive and hope for the compiler to reuse the stack frames. Although I don't think C++ compilers are required to perform this optimization, so all you can do is to rely on implementation.

But why do this if you can simply this_thread::sleep_for()?

ScarletAmaranth
  • 5,065
  • 2
  • 23
  • 34
2

I think the real question should be:

How do functional programming languages like Scheme and Haskell use recursion to achieve looping without causing a stack overflow?

And the answer is: they use a trick called tail-recursion to turn the recursive call into a goto. So you'll have to either find a C++ compiler that implements tail-recursion, or simulate it in your code.

Here's an example to give you an idea of how tail-recursion works:

countdown x = if x == 0
                then 0
                else countdown (x - 1)

countdown 1000000

Notice that, in the recursive step, it just calls the function with different arguments, and then returns its value. So the compiler "cheats" by converting it into code that works like this:

int countdown(int x) {
  start:
  if (x == 0) return 0;
  x = x - 1;
  goto start;
}

By the way, if you have to write your code to take advantage of tail-recursion. It doesn't just automatically work. More information here: What is tail recursion?

Community
  • 1
  • 1
Pitarou
  • 2,211
  • 18
  • 25
  • Yes Exactly that's what I think about , If Haskell can do it , then I want to do it in C++ Just functionally .. and it seems jmp(or goto) is the only solution(cheat) . Thanks – Mostafa 36a2 Jan 01 '14 at 14:03
  • @Mostafa36a2 goto is equivalent to a loop, you're only hiding this and at the same time hoping that the compiler transforms your code, while getting no guarantee for this. That's rather silly, just do it yourself or use standard library functions. – stefan Jan 01 '14 at 14:07
  • 1
    Old Q&A re which C++ compilers support tail recursion here: http://stackoverflow.com/a/34129/24283 – timday Jan 01 '14 at 14:09
  • I know jumping is the main concept of looping , that's not mean I found my expected answer , but that c++ can't illustrate this idea – Mostafa 36a2 Jan 01 '14 at 14:09
0

using a branching recursion. think about a grossly non-optimal recursive fibonacci program. They have exponential running time vs required stack depth.

RichardPlunkett
  • 2,998
  • 14
  • 14
  • fibonacci can be implemented recursivly with linear time , just make the arguments F0,F1,n and you can go through it easily . – Mostafa 36a2 Jan 01 '14 at 13:54
  • 1
    yes yes, but if your goal is to waste time, a function that calls itself twice (with smaller values) is a fine thing. Bad implementation of fibonacci are just the first example I thought of. The fact it has good implementations is thus barely relevant – RichardPlunkett Jan 01 '14 at 13:57
  • oh now I've understand what you want to say "finding an algorithm that's waste time without making SOF" really amazing thinking ! – Mostafa 36a2 Jan 01 '14 at 16:55