Questions tagged [tail-recursion]

Tail recursion is a recursive strategy in which a function does some amount of work, then invokes itself. The "tail" refers to the fact that the recursion is at the very end of the function. Many -- especially functional -- programming language compilers can turn these types of calls into iteration, meaning tail recursion in supported languages can be used without fear of a stack overflow, regardless of the number of calls.

tail-recursion
Filter by
Sorted by
Tagged with
3 votes
2 answers
83 views

Can tail recursion support shorten the stack for other function calls?

Can languages that support tail recursion apply the same technique to non-recursive function calls? For example, if the last thing that function foo does is return the value of calling bar, might ...
Nathan Long's user avatar
4 votes
2 answers
6k views

Is this tail recursion?

I have tried to find examples of tail recursion and I really don't see the difference between regular and tail. If this isn't tail recursion, can someone tell me why its not? public static long fib(...
BluceRee's user avatar
  • 117
1 vote
1 answer
1k views

clang infinite tail recursion optimization

#include <iostream> int foo(int i){ return foo(i + 1); } int main(int argc,char * argv[]){ if(argc != 2){ return 1; } std::cout << foo(std::atoi(argv[...
cfy's user avatar
  • 401
5 votes
1 answer
319 views

F# tail recursive call

I have this code: let rec collect ( t : BCFile list ) ( acc : Set<BCFile> ) : Set<BCFile> = match t with | [] -> acc | hr::tl -> collect ( tl ) ( Set.union acc ( ...
phwp's user avatar
  • 51
8 votes
1 answer
370 views

Tailcalls in Mono

I have some code in F# that works fine under .net but overflows the stack under Mono. A related issue is that it seems to do so long before the stack space supposedly available to it runs out (it is ...
Joe Huha's user avatar
  • 548
1 vote
1 answer
3k views

Multiple recursive calls inside if/else statements and tail recursion

I hope this question is not a dupe. It seems most questions refer to multiple recursive calls in one statement, ie.:return func(n - 1) * func(n - 2). My question involves multiple recursive calls ...
Roberto's user avatar
  • 997
2 votes
1 answer
114 views

Evaluating Performance of Functions

The "oneToEach" function adds 1 to each element of a List[Int]. The first function is not tail recursive, whereas the latter is. If I had a one million length List[Int] that I passed in to these 2 ...
Kevin Meredith's user avatar
1 vote
3 answers
396 views

Why we can't use static variables to achieve tail recursion?

I am learning C, so I am writting some little exercises in C to practice the language. I have experience with functional code, so I love recursion. I think that it would be great to achieve tail ...
Josell's user avatar
  • 1,934
0 votes
1 answer
452 views

Scala tail recursion intersect between 2 lists

I'm pretty new to scala and programming in general (just for fun) and I'm trying to understand tail-recursion and collections but debugg is really hard. I've 2 lists : val quoters = List[Map[String,...
user2648879's user avatar
0 votes
4 answers
1k views

How to implement a pure tail-recursive insert for BST?

All implementations on insert for BST is non-tail recursive. Is that possible to write a tail-recursive insert for BST? If it is possible, how?
Jackson Tale's user avatar
  • 25.6k
0 votes
1 answer
136 views

Tail Recursive function or not

Can anyone help me with this please? (define f (lambda (x) (cond ((null? x) 0) (#t (+ (* (car x) (car x)) (f (cdr x))))))) I couldn't understand if this function is tail recursive or not? ...
user2631892's user avatar
0 votes
2 answers
162 views

Looping Recursive Function c++

I am using Qsort, based on employee.lastname. left is the counter of how many we've ran through. emptotal, (or right) is how many total there are. Since I know there are 5 I forced the pivot point ...
Camber Menschel's user avatar
0 votes
1 answer
2k views

print binary numbers in ascending order

I was trying to print binary numbers in ascending order of 0's (00 then 01, 10, 11). Such that the zeros are before. I tried using the below code from here but this does not give the right op (...
Pradyut Bhattacharya's user avatar
1 vote
1 answer
138 views

Can Strictness Guide Recursion?

Let's say we have a simple tree creating algorithm in Haskell: data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq) makeTree :: Tree Int -> Tree Int makeTree (Node 0 l r) =...
user1104160's user avatar
1 vote
2 answers
3k views

Recursion in Python with Beautiful Soup

So I'm probably just being dumb here and don't understand a basic mechanic of python, but I'm trying to go through and crawl through a webpage, and then get a new link and continue on recursively. ...
Kelan Poten-Coyle's user avatar
2 votes
1 answer
719 views

What is difference between tail recursive and stack recursive functions?

In pure functional languages, say writing factorial function as, fact.0 = 1 fact.n = n*fact.n-1 as this function is stack recursive, could anybody explain difference between stack recursive and tell ...
user avatar
31 votes
2 answers
2k views

Can Tail Call Optimization and RAII Co-Exist?

I can't think of a true RAII language that also has tail call optimization in the specs, but I know many C++ implementations can do it as an implementation-specific optimization. This poses a ...
Louis Jackman's user avatar
1 vote
1 answer
181 views

Local variables in Tail recursion?

I have been reading a lot of articles about tail recursion.But i am still unclear about how the tail recursion uses no stack space. What about the local variables and function arguments? They are ...
Rahul Kurup's user avatar
20 votes
8 answers
15k views

How to think in recursive way?

In order to understand the advanced algorithm concepts like greedy methods and dynamic programming, one first need to be well versed in recursion. I am relatively new to recursion. Whenever a ...
Rahul Kurup's user avatar
14 votes
1 answer
3k views

Scala: Tree Insert Tail Recursion With Complex Structure

I'm creating a tree of custom objects in scala and my insert method throws a stack overflow because it's not tail recursive. However, I can't quite figure out how to make it tail recursive. Related ...
The.Anti.9's user avatar
9 votes
1 answer
492 views

Anything prevents optimizing tail-recursion?

I'm solving a knapsack problem in Haskell using Dynamic Programing. My first attempt was to build a two-dimensional table. But the memory easily gets blown up when the input is large(e.g. a 100 * ...
cfchou's user avatar
  • 1,239
2 votes
1 answer
283 views

Is this not tail recursive? (stack overflow error)

This is a small function I have written to check whether an integer is a prime or not: int prime(int x, int y = 2) { if(y <= x/2) { if((x % y) == 0) return 0; } ...
user1831704's user avatar
1 vote
1 answer
57 views

Broken Tail Recursion?

I have studied programming language course, I have this variant of Scheme code in the slide: ; (listof any) -> (listof any[no-cons]) (define (remove-pairs l) (cond [(empty? l) '()] [...
user1732445's user avatar
14 votes
6 answers
2k views

Prolog performance and recursion type

I was playing with permutation in a couple of programs and stumbled upon this little experiment: Permutation method 1: permute([], []). permute([X|Rest], L) :- permute(Rest, L1), select(X, L,...
lurker's user avatar
  • 57.5k
-1 votes
1 answer
127 views

Deconstructing a recursive process - SICP

Consider the following definition: (define foo (lambda (x y) (if (= x y) 0 (+ x (foo (+ x 1) y))))) What is the test expression? (write the actual expression, ...
user2465378's user avatar
2 votes
2 answers
1k views

Is there a way to break out of @tailrec in Scala?

I have a method that is recursive. Is there a way in scala to break out based on the size of the buffer (as shown below)? A case for breaking out when elementList.size > 5 for example? val ...
user786045's user avatar
  • 2,538
2 votes
1 answer
280 views

Why the following function doesn't generate tail recursion with Clang?

Under clang the following function generates object code for a tail recursive function: template<typename T> constexpr bool is_prime(T number, T limit, T counter) { return counter >= ...
oblitum's user avatar
  • 11.7k
3 votes
1 answer
732 views

What's the most efficient tail recursive prime verification function known?

I was experimenting with meta programming to this point: // compiled on Ubuntu 13.04 with: // clang++ -O3 -ftemplate-depth-8192 -fconstexpr-depth=4096 -std=c++11 -stdlib=libc++ -lcxxrt -ldl compile-...
oblitum's user avatar
  • 11.7k
1 vote
2 answers
472 views

How do I turn a recursive algorithm into a tail-recursive algorithm?

As a first attempt to get into merge sort i produced the following code which works on strings because they are easier than lists to deal with. class Program { static int iterations = 0; ...
user1909612's user avatar
10 votes
1 answer
4k views

Tail recursion in clojure

This is a lisp code that uses tail recursion. (defun factorial (f n) (if (= n 1) f (factorial (* f n) (- n 1)))) I translate this into clojure code expecting the same tail ...
prosseek's user avatar
  • 187k
8 votes
4 answers
8k views

Common Lisp: Why does my tail-recursive function cause a stack overflow?

I have a problem in understanding the performance of a Common Lisp function (I am still a novice). I have two versions of this function, which simply computes the sum of all integers up to a given n. ...
oarfish's user avatar
  • 4,368
2 votes
2 answers
145 views

When executed will this be a tail call?

Once compiled and ran will this behave as a tail call? let rec f accu = function | [] -> accu | h::t -> (h + accu) |> f <| t Maybe there is an easy way to test behavior that I'm ...
Iter's user avatar
  • 361
5 votes
2 answers
1k views

How can I convert this binary recursive function into a tail-recursive form?

There is a clear way to convert binary recursion to tail recursion for sets closed under a function, i.e. integers with addition for the Fibonacci sequence: (Using Haskell) fib :: Int -> Int fib ...
user1104160's user avatar
0 votes
1 answer
899 views

Tail v. Head Recursion

I was wondering if you would identify this as a head or tail recursive function: int exponentiation(int x, int y){ if(!y) { return 1; } return y > 1 ? x * exponentiation(x, y-1) : x; }
user2364260's user avatar
0 votes
1 answer
288 views

Sudoku algorithm with backtracking does not return any solution

i'm a bit stuck with the Sudoku algorithm, i coded it using backtrack, and following the theorical steps this should work, and i tried to debuge it, but is too hard (and yes, it solve some numbers and ...
Santanor's user avatar
  • 566
0 votes
2 answers
757 views

F# lazy recursion

I am have some problems with recursion in Lazy Computations. I need calculation the square root by Newton Raphson method. I do not know how to apply a lazy evaluation. This is my code: let next x z = ...
user2304064's user avatar
1 vote
4 answers
330 views

Is this function really tail-recursive?

I read about recursion in Programming Interviews Exposed (3rd ed.) where they present the following recursive factorial function: int factorial(int n){ if (n > 1) { /* Recursive case */ ...
beta's user avatar
  • 2,480
2 votes
1 answer
3k views

How to Convert Recursion to Tail Recursion

Is it always possible to convert a recursion into a tail recursive one? I am having a hard time converting the following Python function into a tail-recursive one. def BreakWords(glob): """Break a ...
kirakun's user avatar
  • 2,790
1 vote
1 answer
162 views

tail recursion fails (possibly because of implicit cons conversion)

I have what I believe to be a fairly simple tail-recursive function. However, @tailrec tells me otherwise. @tailrec def _next(continue : String, current : List[Long], first : Boolean ) : Stream[...
Martijn's user avatar
  • 12.1k
1 vote
1 answer
543 views

python - traverse a graph (find all issues linked)

I'm bit stuck trying to solve a simple task of getting all linked issues. This is basically a graph task I guess - I take a jira issue, find all its links and then go to linked issues for their links ...
abolotnov's user avatar
  • 4,332
1 vote
1 answer
377 views

"Replacing" an element matching a predicate in an arbitrarily nested List in Scala

I have the following list (just an example - the list can be of an arbitrary depth); val foo = List(1, List(2, List(3, 4)), List(5, List(6, List(7, List(8,9,10))))) I want to traverse the list, and "...
Bob's user avatar
  • 33
1 vote
1 answer
1k views

Postfix expression list evaluation

I have written a program to evaluate a post-fix expression in prolog recursively from an expression list. For example, given the following list: [+,1,2] It should return 3. They way I have ...
thegalah's user avatar
  • 508
8 votes
1 answer
6k views

Tail recursion in gcc/g++

I've tried to search, but was unable to find: what are requisites for functions so that gcc would optimize the tail recursion? Is there any reference or list that would contain the most important ...
dtldarek's user avatar
  • 959
43 votes
3 answers
9k views

Generate tail call opcode

Out of curiosity I was trying to generate a tail call opcode using C#. Fibinacci is an easy one, so my c# example looks like this: private static void Main(string[] args) { Console....
devshorts's user avatar
  • 8,742
1 vote
1 answer
441 views

tail recursion and Boolean operators

I am currently learning F# on my own (via the try f# site). I have the following (imho) tail-recursive function for existential quantification of a unary predicate (int->bool). let rec exists bound ...
D.F.F's user avatar
  • 944
13 votes
1 answer
657 views

why do continuations avoid stackoverflow?

I've been trying to understand continuations / CPS and from what I can gather it builds up a delayed computation, once we get to the end of the list we invoke the final computation. What I don't ...
dusio's user avatar
  • 500
1 vote
1 answer
182 views

Tail recursion - will this make optimal use of frame and how do I check if compiling as tail recursive?

In the below code - quite trivial max and sum of lists - I have a recursive function called at the end of a method. Will the scala compiler treat this as tail recursive and optimize the stack frame ...
JasonG's user avatar
  • 5,872
3 votes
2 answers
1k views

two dimensional tail recursion in scala

I am new to Scala and started to learn about tail recursion. I learned that tail recursion in functional programming is a counter part of iterations (for loops) in imperative programming: Simple C++ ...
tommyk's user avatar
  • 3,247
0 votes
2 answers
601 views

Prolog Sum of All Instances in a List of Facts

I have a list of facts. Each fact defines a relationship between two subjects and the number of projects they've completed. They're defined like this: label(allGroups,[group(a,b,10),group(b,c,3),...
user2217780's user avatar
1 vote
2 answers
415 views

Is this scheme code tail recursive?

EDIT: Thanks to everyone. I'm new to the language(just started using it two days ago), so that's why I'm unfamiliar with conds. I may rewrite it if I have time, but I just wanted to make sure I had ...
user2012892's user avatar

1
19 20
21
22 23
28