Talk:Recursion (computer science)

History

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.

Base Case

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

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

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

Generative (synthetic) recursion

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

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

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

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)

Possible error?

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

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 (talk • contribs) 23:15, 17 May 2009 (UTC)

Java code

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

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

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 (talk • contribs) 17:50, 30 August 2010 (UTC)

Recursion vs. iteration

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)