There is a concept called tail recursion, where the implicit stack is not required and so stack capacity is not an issue.

https://www.geeksforgeeks.org/tail-recursion/

Only if the language/compiler/interpreter/whatever converts it from tail recursive to an iterative loop (which is often done in-place by modifying and reusing the existing stack frame for the next call), which can be done algorithmically since the conversion to a while(TRUE) loop with embedded return is straightforward.

Unfortunately, there is no general algorithm to do this conversion for arbitrary recursive algorithms.

 

Only if the language/compiler/interpreter/whatever converts it from tail recursive to an iterative loop (which is often done in-place by modifying and reusing the existing stack frame for the next call), which can be done algorithmically since the conversion to a while(TRUE) loop with embedded return is straightforward.

Unfortunately, there is no general algorithm to do this conversion for arbitrary recursive algorithms.

Yes, that's true. The F# language is able recognize tail recursion and avoid the stack overhead.

https://cyanbyfuchsia.wordpress.com/2014/02/12/recursion-and-tail-recursion-in-f/

 

Yes, that's true. The F# language is able recognize tail recursion and avoid the stack overhead.

https://cyanbyfuchsia.wordpress.com/2014/02/12/recursion-and-tail-recursion-in-f/

Many compilers do -- GCC does it for tail recursion for all supported languages, including C, and can do it for general (including non-recursive) tail-call functions under certain conditions.

Apparently Python doesn't do tail-call optimization because Guido wants the interpreter to be able to present complete tracebacks when an exception goes unhandled.

But, if you are using Python, you've already made the decision to sacrifice performance for other things.

 

Many compilers do -- GCC does it for tail recursion for all supported languages, including C, and can do it for general (including non-recursive) tail-call functions under certain conditions.

Apparently Python doesn't do tail-call optimization because Guido wants the interpreter to be able to present complete tracebacks when an exception goes unhandled.

But, if you are using Python, you've already made the decision to sacrifice performance for other things.

Are you certain there's no formal proof that any recursive function can always be rewritten as tail recursive? I tried looking years ago and found no definitive yes or no.

 

You are correct, I just asked Bing (chat gtp)!

 

You are correct, I just asked Bing (chat gtp)!

And you just believed it?

I'm pretty sure that there are recursion patterns that simply cannot be written tail-recursively. Potential ones that come to mind are multiply recursive call (the classic example is Fibonacci, but another would be QuickSort).

Many, but I don't think all, singly recursive functions can be made tail-recursive with the use of helper functions or continuations.

 

And you just believed it?

Try it, it gave example of recursion that can't be tailcalled. I didn't just believe it, it explained why.

m pretty sure that there are recursion patterns that simply cannot be written tail-recursively. Potential ones that come to mind are multiply recursive call (the classic example is Fibonacci, but another would be QuickSort).

Many, but I don't think all, singly recursive functions can be made tail-recursive with the use of helper functions or continuations.

Yes, it gave QuickSort as an example.[/QUOTE]

 

It's fine for things like tree and graph algorithms (functional programming) but I'd fire anyone that used it in a critical embedded applications operational logic.

That's sounds rather draconian. Problems that are defined recursively, can be very naturally coded recursively.

 

That's sounds rather draconian. Problems that are defined recursively, can be very naturally coded recursively.

Absolutely draconian but those are the legal rules of safety engineering. Ask Boeing about nuts and bolts.

 

That's sounds rather draconian. Problems that are defined recursively, can be very naturally coded recursively.

Just because you could, doesn't mean you should.

Fibonacci is a great example -- trivially easy to code recursively, since it is defined recursively. Yet even on today's computers, a human can usually calculate the 50th or so number in the sequence faster than the computer because it runs in exponential time. It also has unbounded stack space requirements, which is a HUGE no-no for any critical system software.

 

Absolutely draconian but those are the legal rules of safety engineering. Ask Boeing about nuts and bolts.

Boeing are the last people I'd ask about nuts and bolts, especially door bolts!

 

Just because you could, doesn't mean you should.

Fibonacci is a great example -- trivially easy to code recursively, since it is defined recursively. Yet even on today's computers, a human can usually calculate the 50th or so number in the sequence faster than the computer because it runs in exponential time. It also has unbounded stack space requirements, which is a HUGE no-no for any critical system software.

Well Its only unbounded stack space if the data is unbounded in nature, I'm not advocating careless use of recursion, perhaps if it was used only when it could be tail recursive that would avoid the concern.

I'm not an authority on programming for microcontrollers, so understand the concerns, and as I've said before writing safety or reliability critical software really calls for a very careful choice of programming language anyway.

 

Many, but I don't think all, singly recursive functions can be made tail-recursive with the use of helper functions or continuations.

No, tree and graph traversal algorithms cannot be converted to anything that does not use a stack. Which is basically fake recursion and solves no problem except limited stack space. And, just sets a different limit.

 

[

Well Its only unbounded stack space if the data is unbounded in nature, I'm not advocating careless use of recursion, perhaps if it was used only when it could be tail recursive that would avoid the concern.

I'm not an authority on programming for microcontrollers, so understand the concerns, and as I've said before writing safety or reliability critical software really calls for a very careful choice of programming language anyway.

It's not just for microcontrollers, there are powerful embedded systems (enterprise rack servers running the FSM) controlling 100's of KW of electrical power with deadly high voltage, mechanical systems with deadly and volatile chemicals, per individual machine, worth tens to hundreds of millions, processing billions worth of semiconductors, with the same requirements.

https://www.edn.com/why-misra-c-matters-for-embedded-system-developers/

 

No, tree and graph traversal algorithms cannot be converted to anything that does not use a stack. Which is basically fake recursion and solves no problem except limited stack space. And, just sets a different limit.

True but those are very important problems when programming for specific types of applications that have specific programming rules that ban or severely limit 'real' recursion among other perfectly valid, useful and elegant programming language constructs.

 

[


It's not just for microcontrollers, there are powerful embedded systems (enterprise rack servers running the FSM) controlling 100's of KW of electrical power with deadly high voltage, mechanical systems with deadly and volatile chemicals, per individual machine, worth tens to hundreds of millions, processing billions worth of semiconductors, with the same requirements.

https://www.edn.com/why-misra-c-matters-for-embedded-system-developers/

Yes, I get that. I guess this is more about when is it preferable to use recursion, when does its advantage outweigh the disadvantage.

 

Yes, I get that. I guess this is more about when is it preferable to use recursion, when does its advantage outweigh the disadvantage.

As with most things in engineering, that is very problem specific. It depends on what is critical, preferable, and tolerable for that application. All kinds of factors at play -- ease of development, speed of implementation, portability, maintainability, performance, robustness, safety, and the list goes on and on.

 

Yes, I get that. I guess this is more about when is it preferable to use recursion, when does its advantage outweigh the disadvantage.

Like I said before, my home projects are not limited by MISRA. So I use what makes the programming source clear and understandable for me or what's OK for the project group I'm working with. I don't prefer one of the other usually, what to use comes naturally with the known processor resources, data processing requirements and the source and output data structures.

 

I dug out a tail recursive Fibonacci function written in F#

let fib n =
    let rec tfib n1 n2 = function
    | 0 -> n1
    | n -> tfib n2 (n2 + n1) (n - 1)
    tfib 0 1 n;;

e.g. fib 23 gives the result 28657

 

Other than seeing if a possible new hire can code a recursive routine, what's the prime use of the Fibonacci function in practical programming?

I've seen hardware implementations for a RNG in some old crypto equipment.



https://en.wikipedia.org/wiki/Lagged_Fibonacci_generator