The recursion tag has no wiki summary.
2
votes
0answers
49 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 the ...
0
votes
0answers
67 views
Time bound for recursive algorithm with constant combination time [closed]
Suppose I have a recursive algorithm that splits input into 2 inputs of size n-1 and solves them recursively. It combines the results in a constant time say c.
So formulating an equation for this,
...
4
votes
2answers
187 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
90 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, ...
8
votes
6answers
892 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 ...
-2
votes
1answer
90 views
Is this the right strategy to convert an in-level order binary tree to a doubly linked list? [closed]
So I recently came across this question - Make a function that converts a in-level-order binary tree into a doubly linked list. Apparently, it's a common interview question.
This is the strategy I ...
3
votes
2answers
647 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
320 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 ...
0
votes
0answers
138 views
Would dynamic programming help reduce the number of recursive steps [closed]
Consider the following recursive function to compute the number of ways to form
combinations of N things taken R at a time:
...
8
votes
3answers
649 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?
