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.

Filter by
Sorted by
Tagged with
-2 votes
1 answer
26 views

Why does it not work ? Can Someone please explain Memory Allocation, static/non static, global/local variables/ deepcopy used in stack

It is a simple recursive function to print array elements in reverse. When I call the function above the print statement, it gives me index -1 outOfBoundException. When I print before calling the ...
Dhruv Chopra's user avatar
0 votes
1 answer
31 views

Is tail call (including tail recursion) compiler/implementation dependent?

Searching tail recursion on the internet I stumbled on How does compiler know whether the recursion is a tail recursion or not and how does it optimize tail recursion. If I understand correctly then ...
duong_dajgja's user avatar
  • 4,196
-1 votes
1 answer
39 views

How to change this nested recursion to linear recursion?

I want to change this function of nested recursion to linear recursion or optimally is tail recursion. long long x(int n) { if (n == 0) return 1; int ret = 0; for (int i = 0; i < n; ++i)...
HCMUSer's user avatar
  • 19
1 vote
1 answer
44 views

How to write a recursion function using 2 accumulators?

I'm new to Python and recursion is a foreign thing to me. For my assignment I have functions that involve tail recursion, a while loop, or a generator as specified by _t, _w, or _g if the function ...
mamelody's user avatar
0 votes
0 answers
57 views

Is there a gcc flag that just optimizes the tail calls?

This is an appeal for help with the gcc optimization flags. I have studied other similar questions to some extent before asking this question. I am working with a high school student to understand the ...
Kedar Mhaswade's user avatar
0 votes
1 answer
36 views

Trying to optimize the code using @tailrec but failing

I want to use @tailrec in Scala to convert the code to tail recursive but I get an error saying the function is not in the tail position but I disagree with the conclusion of the compiler. I ...
Node.JS's user avatar
  • 990
0 votes
0 answers
57 views

gcc can't optimize tail recursion of a std::vector<int>, exit with code 139?

I have this program: #include <iostream> #include <vector> int foo(std::vector<int> bar) { if (bar[0] == 0) return bar[0]; else { bar[0] -= 1; ...
justANewb stands with Ukraine's user avatar
0 votes
3 answers
68 views

Idiomatic Scala way to traverse Iterator-like data structure

Given a class from a legacy library that behaves like an Iterator such that you can traverse it's content with hasNext and next but it does not implement the Iterator interface: class LegacyIterator[T]...
Zwackelmann's user avatar
0 votes
1 answer
69 views

How to remove last node of a linked list (Python)

The goal is to remove the last node of a linked list. (Python) The code that I have written only added to the list instead of taking the tail away. I'm not sure if the error is coming from this part ...
BRN's user avatar
  • 1
2 votes
2 answers
126 views

Stack overflow or tail recursion?

I'm trying to find out if the following code piece is good or bad practice. It's about a html query string that should be parsed by my API. It's very convenient to use recursion to trim an arbitrary ...
glades's user avatar
  • 3,231
1 vote
2 answers
134 views

tail recursion to add element to end of list in Haskell

I wrote this simple function to append an element to the end of a list recursively: --takes arguments x and lst and appends x to the end of list append1::a->[a]->[a] append1 x [] = x:[] append1 ...
floxam's user avatar
  • 25
1 vote
1 answer
104 views

Converting a simple recursive haskell function to be tail recursive

2 weeks new to haskell and functional programming. In the process of covering foldl and foldr in class, I found that I was quite new to tail recursion and never actually tried writing a tail recursive ...
floxam's user avatar
  • 25
4 votes
2 answers
162 views

Automatically detect whether a Haskell function is tail recursive

I'm currently writing an auto-grader for a Haskell course. For the section on "tail-recursion", I need a way to automatically and safely detect whether a given Haskell function is tail-...
Mobin's user avatar
  • 49
2 votes
1 answer
105 views

Tail-recursive string splitting in Haskell

I'm considering the problem of splitting a string s at a character c. This is expressed as break (c ==) s where the Haskell library definition of break (c ==) close enough to br [] = ([],[]) br ...
Jay's user avatar
  • 175
0 votes
0 answers
93 views

Recursive Function - RangeError: Maximum call stack size exceeded - JavaScript

I'm trying to make a set of functions that add the digits of a number. But with giant numbers, the maximum amount of calls is exceeded. I would like to resolve this issue. My code - (Example of error ...
Lucas Junqueira's user avatar
0 votes
2 answers
49 views

Scala calculate the amount a certain object appears in a sequence

I am new to Scala and i am trying to create a function that calculates the amount a certain object appears in a sequence. So in this case we have a sequence with 1 Hippo and 3 Tigers in it. I want the ...
Jest Inestesa's user avatar
2 votes
1 answer
105 views

How do I turn this recursion into tail recursion?

With given array on unique numbers which are always greater than 0 I need to find all possible unique combinations of those numbers that are equal to a certain number when summed. For example, ...
queques's user avatar
  • 21
2 votes
1 answer
147 views

What's the difference between tail and guarded recursion?

In my exercise I have to decide what kind of recursion the functions are. We have to choose from linear recursion, tail recursion and guarded recursion but I don't really understand the difference ...
immi0815's user avatar
0 votes
0 answers
39 views

why recursion not breaking at end in java

I just started learning recursion in Java but I can't understand how recursion is working. But it looks like three line code. Is there any easy way to learn recursion, nested recursion, deep learning ...
sleep's user avatar
  • 1
0 votes
0 answers
73 views

How to make this function tail-recursive?

Suppose I've got fetchPage API that fetches a page of data and returns a Future, for instance case class Page(data: Seq[String], currentPage: Int, hasNext: Boolean) def fetchPage(pageNum: Int): ...
Michael's user avatar
  • 40.7k
0 votes
0 answers
141 views

JSONata returns Stack Overflow error when using functions on a non-first property in a new grouped object

I am unsure if this stems from JSONata 2.0.0 but I have yet to see this from previous uses of this query language. I have a list of objects that the sub-arrays will contain the same dates: { property1:...
Jesse Benjamin Slomowitz's user avatar
0 votes
3 answers
110 views

Tail call optimization with a function returning a tuple

I have a simple function that splits a list at an index: let rec split_at ls i = match i with | 0 -> ([], ls) | _ -> match ls with | [] -> raise Not_found | h::t -> ...
mushroom's user avatar
  • 6,141
0 votes
1 answer
58 views

Why does clang have trouble with optimizing tail calls in destructors?

Here is a simplified singly-linked list, where each node owns the next, along with a function for destroying the list: struct Node { Node* next = nullptr; ~Node() { delete next; } }; void ...
jacobsa's user avatar
  • 5,679
2 votes
3 answers
81 views

Tail Recursive Binary Tree Search Function JS

I'm trying to write a tail recursive function contains(tree,element) that returns true if the element exists in the Binary tree, false otherwise. I wrote the recursive function, the problem is that I ...
Grinza's user avatar
  • 48
-1 votes
1 answer
44 views

using print() after invoking recursion

Can Someone tell me what exactly is happening here.Is the print statement executing after all the draw [3,2,1] are completed or it's happening simultaneously.I tried adding print(n) but still couldn't ...
jack_'s user avatar
  • 11
0 votes
1 answer
90 views

Prolog tail recursion for Fibonacci sequence

I have been trying to make a Prolog tail recursion for Fibonacci sequence, but I have a lot of trouble making the code, this is kinda what I was doing and I'm not sure if I'm going the right path ...
Luc4s_mp's user avatar
2 votes
0 answers
66 views

Prolog recursive method printing out and returning different things. Possible issue with tail recursion

I am having trouble with a recursive function in Prolog. The main expand function seems to be working fine. But when it reaches the base case when one of the lists is empty it prints out the correct ...
garrett_17's user avatar
0 votes
0 answers
32 views

Tail and head recursion questions [duplicate]

I recently started learning about tail and head recursion and there are a couple of questions I'd like to ask. In the tailRec function below, the program prints a new line when tailRec(0), the ...
Faizaan A.'s user avatar
0 votes
1 answer
53 views

How can I do a combinatory number function in OCaml

So the thing is i want to do a combinatory number function in OCaml and I have the following code: let rec fact: int -> int = fun num -> let rec help: int -> int -> int = fun n acc -> ...
WizzzStark's user avatar
1 vote
3 answers
121 views

Can someone explain this recursion problem to me? (Factorial)

Edit - I have solved this problem but if its okay, I would like the experts here to still explain this problem so that other beginners could learn. You would do a way better job explaining. I'm trying ...
Hakari Kinji's user avatar
0 votes
2 answers
179 views

How to rewrite this function to be tail-recursive?

I'm reading the book The Little Schemer, I implement the functions in Clojure, How to rewrite this function as a tail-recursive function in Clojure? (defn rember* [a lat] (cond (empty? ...
dex's user avatar
  • 3
0 votes
1 answer
129 views

Implement function with tail recursion

I have this ADT for representing expressions: trait Expression { def value: Int } case class Number(value: Int) extends Expression case class Add(a: Expression, b: Expression) extends ...
M.G.'s user avatar
  • 359
0 votes
1 answer
59 views

Tail recursion of the level order traversal using a predefined function signature

my question is how to use tail recursion to traverse the binary tree in the level order and print it in a specific format. Binary Tree __ 60 _ | | __ 50 _ 100 _ ...
Willi's user avatar
  • 317
2 votes
1 answer
75 views

Why is compiler considering this function non tail recursive?

I'm solving problems posted in one of the OCaml tutorials. One of them is to write a function that will calculate the length of the list. It should be tail-recursive. The naive, non tail-recursive ...
kamituel's user avatar
  • 34.3k
0 votes
1 answer
67 views

Total possible outcomes for coin flip

For a given coin which is tossed 'n' times, find the 'count' of total possible combination of outcomes using recursion. I have successfully printed the outcomes using this code: public class Main { ...
jazz's user avatar
  • 3
2 votes
0 answers
130 views

Tail recursion to get data from paginated get API

Some APIs offers paginated data. I want to call the API and retrieve the data of all pages. I was thinking an implementation of it using recursion. I will call it to retrieve the first page data and ...
M.G.'s user avatar
  • 359
1 vote
1 answer
55 views

recur when mapping over a nested vector

Is my understanding of tail end optimization correct that map can't be used with tail end optimization? So if I wanted to use tail end optimization, I'd had to find a different algorithm: (defn ...
iGEL's user avatar
  • 16.3k
0 votes
0 answers
37 views

Why my tail recursive code is not running in my pc

I have written a simple tail recursive modular exponentiation function like this : #include <bits/stdc++.h> using namespace std; #define mod (1000000000+7) #define ll long long ll modexp(ll x,...
akib35's user avatar
  • 3
3 votes
1 answer
171 views

Tail recursion fibonacci derived from linear recursive version using Burstall & Darlington's folding/unfolding system

The inefficient (tree-recursive) fib(n) function calculates the n-th Fibonacci number. In Haskell: fib 0 = 0 fib 1 = 1 fib n = fib (n - 1) + fib (n - 2) Using the following identity: gfib(n) = (fib(n)...
Ricardo Pérez's user avatar
1 vote
1 answer
119 views

Tail recursion optimized javascript code performance worse than non optimization, it's counterintuitive,Is it because the compiler doesn't optimize? [duplicate]

function factorialNormal(n) { if (n === 1) { return n } return n + factorialNormal(n - 1) } function factorialWithTail(n, acc) { if (n === 1) return acc; return factorialWithTail(n-1, n ...
makmav's user avatar
  • 55
1 vote
2 answers
171 views

tail recursive version for Fibonacci-like function

I am having trouble understanding the concept of tail recursion, I want to make a tail recursive version for Fibonacci-like function, p1= n-3 , p2= n-2, fx( p1 ) + fx( p2 ) and so far this is what I ...
cealex's user avatar
  • 173
0 votes
2 answers
40 views

Clarification on tail recursive methods

Is the following method tail-recursive? I believe that it is not tail recursive because it relies on the previous results and so needs a stack frame, am I correct to state this? public int[] fib(int n)...
Parzival's user avatar
2 votes
2 answers
230 views

Haskell extremely slow simple recurrence

I'm experimenting with Haskell profiling with a simple recursive max algorithm: max_tag :: Integer -> [Integer] -> Integer max_tag head [] = head max_tag head (x:xs) = let {m = max_tag x xs} ...
OrenIshShalom's user avatar
-1 votes
1 answer
40 views

Why is this recursive script returning 'None'? [duplicate]

The code below is intended to use the number of aces and the number of points you'd have if the aces were low in blackjack and make the list of numbers you could pick to have by changing if the ace is ...
Skellybob's user avatar
0 votes
1 answer
45 views

Tail-recursive list of divisors of an integer in prolog

I am trying to make a simple tail-recursive loop to collect the divisors of an integer, divisors(N,List) and its working when List is not instantiated, for example, ?- divisors(14,What). What = [2, 7]...
PaulM's user avatar
  • 171
0 votes
3 answers
514 views

Scala: How to uppercase every other letter

I was asked this question in an interview. She wanted the answer in scala not java. My answer was java centric. Note that you can NOT use the character index to decide whether to uppercase and ...
mbsf's user avatar
  • 119
3 votes
1 answer
107 views

when to use tail call optimization in a cairo smartcontract

I can often make a terminal recursive version of my functions with a little less elegant code. Should I do it because it could reduce the fees or should I keep the unoptimised version? For example, ...
Th0rgal's user avatar
  • 663
0 votes
2 answers
91 views

Out of memory when use for loop to input parameter in recursive function Python

I have a recursive function: def recursive_func(parameter1): ..... if __name__ == "__main__": list_parameter_input = [a,b,c,d,e] for item in list_parameter_input: ...
Toan Nguyen Phuoc's user avatar
1 vote
3 answers
146 views

Can I use `recur` in this implementation of function composition in Clojure?

Consider this simple-minded recursive implementation of comp in Clojure: (defn my-comp ([f] (fn [& args] (apply f args))) ([f & funcs] (fn [& args] (f (apply (apply my-...
Schiphol's user avatar
  • 1,081
1 vote
3 answers
185 views

Recursive approach for building a tree like object hierarchy does not work as expected

I'm trying to write functionality something like this: Input: ['A', '-B1', '--B2', '-C1', 'D'] Output: {'A': {'B1': {'B2': {}}, 'C1': {}}, 'D': {}} As you can see that B1 and C1 are children of A ...
Saurav Kumar's user avatar

1
2 3 4 5
27