# Questions tagged [tail-recursion]

The tag has no usage guidance.

11 questions
Filter by
Sorted by
Tagged with
163 views

### Tail call optimization via translating to CPS

I am struggling to wrap my head around this compiler technique, so let's say here's my factorial function ...
• 235
50 views

### Structural induction proof for reverse(push(as, bs)) = push(reverse(bs), reverse(as))

I need to prove: reverse(push(as,bs)) = push(reverse(bs), reverse(as)) where: ...
4k views

### Why is tail recursion better than regular recursion?

There is the axiom you should always prefer tail-recursion over regular recursion whenever possible. (I'm not considering tabulation as an alternative in this question). I understand the idea by why ...
• 251
28 views

For example exist linked list with thousands (maybe million) elements or very deep tree which some branches are very long and have only one child, but exists other short branches with many children. ...
• 141
190 views

### Loop optimization of non-tail recursion

When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form: ...
105 views

### Are some algorithms inherently recursive?

Are some algorithms inherently recursive? As in, rewriting it in tail-recursive/iterative form with a stack is still needed, and there is no way to do it otherwise. I am asking because I struggled to ...
• 125
464 views

### Tail recursion can't work with dynamic programming programs

I am doing some exercises on dynamic programming in order to get familar with this concept. I've noticed that most of the time it's not difficult to calculate the complexity of a program using dynamic ...
• 31
1k views

### What property of cons allows elimination of tail recursion modulo cons?

I'm familiar with the idea of basic tail recursion elimination, where functions that return the direct result of a call to themselves can be rewritten as iterative loops. ...
• 263
4k views

### Stack depth for QuickSort

CLRS Problem : 7.4 How does Tail-Recursive-QuickSort improve the efficiency of quick sort any better ? Original quicksort Tail recursive quicksort Question ...
• 101
1 vote