Talk:Recursion (computer science)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Top-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Top  This article has been rated as Top-importance on the project's importance scale.
 
WikiProject Mathematics (Rated C-class, Mid-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
C Class
Mid Priority
 Field:  Foundations, logic, and set theory


History[edit]

I think it would be cool to have a paragraph to recognize the fathers of the science of recursion. von Neumann is a likely lead, but haven't found any primary sources just yet. — Preceding unsigned comment added by 165.234.0.138 (talk) 14:18, 10 April 2012 (UTC)

Base Case[edit]

Base case redirects here. Would it not be helpful therefore to have a clear definition of the term, 'base case'? —Preceding unsigned comment added by 82.138.219.211 (talk) 23:50, 13 February 2010 (UTC)

Just added. 76.191.222.13 (talk) 09:26, 20 June 2010 (UTC)

WTF? Does the existence of a decades-old 1-minute bass solo really deserve to be mentioned at the top of this page? Is there an official WP rule that says every trivial alternative usage needs to be spelled out? - Frankie1969 (talk) 20:35, 8 September 2010 (UTC)

Recursive Procedures and Processes[edit]

Wouldn't it be a good idea to include some information about Recursive procedures and processes? (as in [1]) --Kamitsaha (talk) 12:03, 7 February 2009 (UTC)

Arm's-Length Recursion[edit]

Should there be something about arm's length recursion in this article? -- Skaraoke 01:26, 2 March 2007 (UTC)

Good point – thanks! Done – see Arm's-length recursion.

—Nils von Barth (nbarth) (talk) 07:22, 7 December 2012 (UTC)
How is this different from just enlarging the base case(s), e.g. recursion unrolling? I also notice that this section is unsourced. (Google finds very few usages of this term outside of Wikipedia and copies thereof.) — Steven G. Johnson (talk)

Generative (synthetic) recursion[edit]

It would be nice to have a simple code example for generative recursion.

--84.9.82.184 16:31, 26 April 2007 (UTC)

GCD and Towers of Hanoi are definitely generative. However, a bigger problem with the page as it stands is that the factorial and fibonacci algorithms given are structurally-recursive, though the header implies they're generatively-recursive. (The structure on which they operate is that of the natural numbers, defined as zero or n+1 where n is a natural number.) So they should be moved to the structural section. 76.191.222.13 (talk) 09:29, 20 June 2010 (UTC)

Hodge-podge of languages used in Wikipedia[edit]

I realize that every programmer has his/her own favorite language, but reading a programming-related article that switches from one language to another is ridiculous and unnecessary. Does anyone object to re-writing each of the algorithms in a single language? I propose either Python or Java, since they're both very widely used.

-Why use a programming language at all? Programming examples should simply be written in pseudo-code, in my opinion. -Adam —Preceding unsigned comment added by 216.125.160.51 (talk) 22:00, 2 June 2008 (UTC)

FYI, the current Manual of Style draft for code samples and algorithms can be found here: (Note that I don't agree with everything that is currently written in this draft.) Wikipedia:WikiProject_Computer_science/Manual_of_style_(computer_science)#Style_guidelines
In my opinion we should provide pseudo-code and a single programming language that is well known to a broad audience. Pseudo-code can help in case someone does not understand the provided programming language example. However, for many people it is not always easy to translate pseudo-code into their favourite programming language. Many autodidactic programmers did not learn programming by studying pseudo-code first and might never have seen it before. An example that "compiles out of the box" is often much more helpful.
If possible, I suggest using C because it is relatively old (but still around and important) and it is taught in a number of schools and universities. Many modern languages such as C++, Java, C# and JavaScript are derived from it, share a similar syntax and thus belong to the C-family of languages. It is often trivial to translate algorithms in C code to Java. Other programming languages such as functional (e.g. Scheme) or dynamic languages (e.g. Python) should be used for instance if a specific concept or language construct is needed in the example but not available in C. Ghettoblaster (talk) 09:19, 3 June 2008 (UTC)

Complexity of recursive functions[edit]

Is it possible to give general statements about the complexity (Big O notation) of recursive functions? --Abdull (talk) 12:29, 11 August 2008 (UTC)

Yes - see recurrence...a good example of it being applied to determine complexity is here: http://www.cs.duke.edu/~ola/ap/recurrence.html —Preceding unsigned comment added by 68.40.187.164 (talk) 05:49, 17 February 2009 (UTC)

Factorial Implementations for n=0[edit]

The example programs should check for n==0 rather than n==1. Currently they simply crash when input is 0. (They shouldn't because fact(0) is defined 1 in the fact function definition.) --80.66.6.99 (talk) 13:05, 22 August 2008 (UTC)

Done. --Quuxplusone (talk) 08:00, 24 August 2008 (UTC)
Wouldn't checking if n <= 1 be better? I agree that n == 1 is incorrect, but n == 0 adds a needless cycle for input > 0 (e.g., for 3! it computes 3x2x1x1 instead of 3x2x1). 142.20.20.193 (talk) 16:19, 7 April 2015 (UTC)

Possible error?[edit]

In this article, it gives an example of recursion as follows:

"To make a very literal example out of this: If an unknown word is seen in a book, the reader can make a note of the current page number and put the note on a stack (which is empty so far). The reader can then look the new word up and, while reading on the subject, may find yet another unknown word. The page number of this word is also written down and put on top of the stack. At some point an article is read that does not require any explanation. The reader then returns to the previous page number and continues reading from there. This is repeated, sequentially removing the topmost note from the stack. Finally, the reader returns to the original book. This is a recursive approach."

However, this seems more like a standard series of function calls...it doesn't seem to be "calling itself" in any way.

68.40.187.164 (talk) 04:38, 17 February 2009 (UTC)

More complex examples[edit]

All examples in this tutorial can be rewriten using simple while loop. All presented exaples are recursions of same category. None of current examples show true strength of recursion.

Number of examples whit recursion of same type can be reduced. Complex examples should be added, for instance: Simple brute force (for instance Catalan's_problem solving) Searching filename in directories tree .. —Preceding unsigned comment added by Rahulov (talkcontribs) 23:15, 17 May 2009 (UTC)

Java code[edit]

The current Java code for Fibonacci numbers just outputs 1 no matter what was inputted, doesn't it?

Since k decreases each time, it will eventually hit 2. When it does so, the function returns 1 and does nothing else. 174.57.188.50 (talk) 03:54, 24 December 2009 (UTC)

No. Eventually k hits 2 or lower and returns 1, but that value is returned to the function that called it...which may well be the function itself. This is the essence of the recursion in this example: the function calls ITSELF and uses that value to compute the fibonacci number for the k it was given, which it then passes back on up the chain.
If I call fib(3), it will in turn call fib(2) and fib(1). Both of these will return 1, but they will return 1 to the fib(3) call, which adds them together and gets 2, indeed the correct value for k = 3.
This program is, however, rather bugged. If you compute fib(0), you get 1, which is incorrect. It ought to have a second base case to account for this. 76.121.28.181 (talk) 13:50, 14 March 2010 (UTC)
    /**
     * Recursively calculate the kth Fibonacci number.
     *
     * @param k indicates which Fibonacci number to compute.
     * @return the kth Fibonacci number.
     */
    private static int fib(int k) {

	// Base Case:
	//   If k <= 2 then fib(k) = 1.
	if (k <= 2) {
	    return 1;
	}
	// Recursive Case:
	//   If k > 2 then fib(k) = fib(k-1) + fib(k-2).
	else {
	    return fib(k-1) + fib(k-2);
	} 
    }

Java, C and tail recursion[edit]

The article wrongly claims that neither C nor Java optimize tail recursion.

I just ran this test on my default OSX-installed JVM, and it shows that the code was transformed into its non-recursive equivalent: http://www.ibm.com/developerworks/java/library/j-diag8.html. Similarly, there's plenty examples online that show that GCC can not only optimize tail-recursive calls, but also quasi-tail-recursive calls, as in the naive definition of fibonacci. 130.92.9.56 (talk) 12:22, 29 July 2010 (UTC)

I think the issue is you are identifying "tail recursion" with compiler optimization. In the Scheme language, for example, all conforming implementations must optimize tail recursion so that it does not consume stack space. This is part of the language and programmers can rely on it. In C and Java, some compilers may do the optimization, but it is not part of the language specification, and programmers cannot rely on it. Moreover, in Java, it is generally considered impossible for an implementation to support the security model and also optimize tail calls. This issue with Java has been discussed to death all over the web; there seem to be rumors that Java 7 might have some support. — Carl (CBM · talk) 14:54, 29 July 2010 (UTC)

Not enough about termination and recursion problems[edit]

Recursion is a major cause of problems in software applications.

The article needs to emphasize that a termination condition is essential or the algorithm is not recursion - it is an infinite loop and a run-time failure.

Diagnosis and debugging techniques for recursion problems (such as stack overflow) would also be good to add. —Preceding unsigned comment added by Brutzman (talkcontribs) 17:50, 30 August 2010 (UTC)

Recursion vs. iteration[edit]

Quote: "If your problem requires evaluating properties and then processing depending on those properties, recursive solutions will most likely involve cumbersome conditional statements whereas an iterative solution would intuitively process each case."

Run that by me again ...

- Does the phrase "evaluating properties and then processing depending on those properties" say anything more than the simple term conditional processing or conditional execution?

- What is "cumbersome" about a conditional statement?

- How exactly would an iterative solution "intuitively" perform conditional processing without any conditional statements?

John lindgren (talk) 18:22, 17 June 2011 (UTC)

The concept is messy![edit]

"Recursion" is a mathematical method, not "computer science". That nowadays numerical mathematical computations are made with computers is another matter. There is absolutely no connection between the availability of "recursive procedures" in a computer language and the use of a recursive algorithm, a "do loop" does it just as well(more efficiently)!

Most of this material should be "Recursion(mathematics)"

Then there will be left some other material for "Recursion(computer science)" like "recursive procedures" with the procedure(subroutine) calling itself and other similar matter

Stamcose (talk) 09:57, 7 January 2013 (UTC)

Section 'Fibonacci' is a total mess[edit]

Most of the section is written in a highly un-encyclopedic tone (talk of "gray matter computers" and "soft tissue," abbreviation of "Fibonacci," what appears to be an attempted pun in the phrase "or even to re-curse @#$%^& at all,") and a gigantic list of the same algorithm in tons of different programming languages. It looks like it needs a serious rewrite, but I don't feel familiar enough with the topic to do so myself. 72.82.63.137 (talk) 23:22, 24 February 2013 (UTC)

I agree completely. This section was a discursive, unencyclopedic essay with no reliable sources. I have removed it, following WP policies about essays and original research. Also, the numerous code examples were not helpful. The following section on the Euclidean algorithm for GCD is not much better, but at least it is a little more compact. Also, both Fibonacci and GCD have the inconvenient property (for the purposes of this article) that they are more easily and more efficiently calculated iteratively.... --Macrakis (talk) 00:13, 25 February 2013 (UTC)

Hierarchy of recursion types[edit]

Does anyone know of a comprehensive hierarchy of recursion techniques? I found the following hierarchy pdf that covers just list processing:

Recursive list processing technique
    element technique
    list technique
        naive technique
        accumulator technique
        railway-shunt technique
        inverse naive technique
    position technique
    combination technique

I think making the different types of recursion explicit would improve the article. pgr94 (talk) 13:48, 21 March 2014 (UTC)

Examples[edit]

The current examples are weak. Almost all of them are as just as naturally (or more so!) expressed iteratively (factorial, gcd, binary search, list traversal). The Towers of Hanoi example, rather than presenting the algorithm for moving the disks, just presents the calculation of the count of moves, with no explanation or motivation. There are no examples of mutual (or multiple) recursion; a simple example would be a symbolic differentiation program for expressions involving + and *. --Macrakis (talk) 10:53, 9 February 2015 (UTC)

Else in "Example implementation of binary search in C"[edit]

Would anybody object if I were to remove the "else" reserved words in the "Example implementation of binary search in C" code? It always makes my Agent Orange act up when an else follows a return inasmuch as the else is redundant and no considered "best practices." Damotclese (talk) 21:26, 22 October 2015 (UTC)

You surely don't mean Agent Orange, but some lint-like program by that name. Anyway.
I find that the else-if's make the structure of this code far clearer than a sequence of if/returns. They let you see at a glance that only one of the clauses will be executed. --Macrakis (talk) 22:48, 22 October 2015 (UTC)

Books about recursive programming[edit]

I added Introduction to Recursive Programming to the list of monographs on recursive programming. My edit was undone because the book was previously removed due to self promotion by the author. This latest publication on the topic is a valuable resource that should be included. Bkthfrst (talk) 03:54, 3 October 2017 (UTC)

Can you give a reason for your claim? Why is the resource valuable? - Jochen Burghardt (talk) 05:01, 3 October 2017 (UTC)
It is a comprehensive introduction to recursive programming. Unlike the other books in the list, its code examples are presented in Python, which is an increasingly popular language for computer science education, as well as scientific and commercial applications. The code examples are available for free, without purchase of the book. Bkthfrst (talk) 21:19, 3 October 2017 (UTC)