The tag has no wiki summary.

learn more… | top users | synonyms

-4
votes
0answers
26 views

Solving the following recursions using the Akra-Bazzi theorem [closed]

Can the following equations be solved using the Akra-Bazzi theorem and how? Also - I don't quite understand the h_i(x) part of the Akra-Bazzi theorem in Wikipedia. I'll appreciate an explanation. ...
-1
votes
0answers
58 views

Making a function tail-recursive without using CPS

Is there a way to compute $\binom{n}{k}$ through the recurrence $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ in a tail-recursive manner using only the basic structures found in mainstream ...
5
votes
1answer
74 views

Extending simple types to allow `fix`

I'm reading some lecture notes saying that “fix cannot be defined in the simply typed lambda-calculus” and that “no expression that can lead to non-terminating ...
4
votes
2answers
140 views

Higher order Quines - when do super Quines exist?

The normal Quine - a program that prints its own code - is a special case of an n-Quine. An n-Quine is a program that prints code for a different program that after n iterations of printing and ...
0
votes
1answer
215 views

Difference between a cyclic and a left-recursive context-free grammar?

I am currently reading a paper indicating that a cyclic CFG and a left-recursive CFG are different things: The original purpose of the LC transform is to allow simulation of left-corner parsing ...
2
votes
1answer
160 views

recursion schemes that prune

Probably the most common recursion scheme is the catamorphism, or fold. This is a recursion that takes a data type and "deconstructs" it into something else. For example, we can calculate the length ...
5
votes
1answer
310 views

Trampoline that automatically balances heap and stack

While working through Fogus' Functional Javascript, I came across the trampoline function, which can be used to make safe recursive functions that don't blow up the stack. In Fogus' words, "Of course ...
5
votes
2answers
224 views

Does “Productive function” mean just that in ME O'Neill, The Genuine Sieve of Eratosthenes?

M.E. O'Neill in the Epilogue of "The Genuine Sieve of Eratosthenes" (preprint http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf DOI 10.1017/S0956796808007004) quotes Richard Bird that "union is ...
4
votes
2answers
200 views

Mathematical explanation of recursion and lambda (referenced in The Little Schemer)

In the preface of Friedman and Felleisen's book The Little Schemer it states: We could, for example, describe the entire technical content of this book in less than a page of mathematics, but a ...
2
votes
0answers
98 views

Recursion Schemes for Static Analysis (AST)

In the process of creating an AST analysis framework one of the challenges is creating good reusable functions and to avoid too much boiler-plate code. To that end catamorphisms seem like a good fit, ...
9
votes
6answers
1k views

Removing recursion - a look into theory behind the scenes

I am new to this site and this question is certainly not research level - but oh well. I have a little background in software engineering and almost none in CSTheory, but I find it attractive. To make ...
3
votes
2answers
911 views

Stack memory usage for tail calls

I'm puzzled by this statement from Wikipedia: For tail calls, there is no need to remember the place we are calling from — instead, we can perform tail call elimination by leaving the stack ...
5
votes
1answer
347 views

Parallel solution of recurrence equation

One of the most well known parallel algorithms for the solution of recurrence equations is the one proposed by Kogge and Stone (it can be found here). They proved that all recurrence equations of the ...
9
votes
3answers
815 views

About recursion

Where did the idea of recursion originated from? I mean first who thought about it.Can anybody care to explain about the origin of recursion and subsequent impact on the computer science?