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. — Preceding unsigned comment added by 165.234.0.138 (talk) 14:18, 10 April 2012 (UTC)

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)

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

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)

Just to be contrarian...why not have a ton of examples (maybe on other pages)

I don't think that code examples are going to fill up Wikipedia to the bursting point. I would encourage good examples in a range of languages. This serves several purposes:

• Beginning learners are often struggling to learn even the basics of syntax and having an example in 'their' language makes it much more approachable.
  • Recursion is a difficult subject for some students to wrap their head around. Consider having more than one example in a given language.
    • This is where having additional pages would be helpful, but can someone else suggest a template, please?
• It is a way to help those who are looking at different languages appreciate styles. As someone who has had to debug a C program written in Java...it can be a clash of cultures. While there isn't always a huge different in the syntax of a C and Java program, the semantics and style are quite distinctive and authors of examples should be encouraged to write 'pythonic' Python (perhaps w/ different libraries), and whatever the preferred style for BASH, C++, JavaScript/TypeScript (w/ various frameworks, both server side and in-browser), C#, Objective-C, Java, Julia, Swift, Scala, BASIC, C, D, Guile, Mumps, FORTRAN, Pascal, Brainfuck, etc. etc.
  • It would be good to have examples with generics/templates and without.
    • We can skip commercial languages. If we need to focus, it should be on GCC languages, Python, BASH and JS.
  • Authors should use comments to illustrate the steps and point out language features and idioms in use (e.g. if using a GoF pattern, probably should you are using a design pattern).
• Recursion is a great example where the choice of language really matters. So doing basic regression test and comparison between languages can be very informative.
  • Remind me how high you can go with Fibonacci numbers before the JVM crashes when it runs out of memory?
• Creating a separate page for examples would be best if someone can find/make a template so it can get the needed metadata and indexed as Wikidata.
• A pictures is worth 2¹⁰ words. Consider simple flow charts and UML2 to go with your source.

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)

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?

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)

The concept is messy!

"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

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

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

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"

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

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)

how to Design Programs

The embedded reference to this book in the article feels like advertising, especially by referring to it by an abbreviation. Sure this should be rewritten and simply cited? --158.180.128.10 (talk) 15:41, 7 February 2018 (UTC)

Are you waiting for an answer to do it? If so, then YES. (It is a very good intro to CompSci), and when I read it for an into comp sci taught by Mathew Flatt, one of the authors, it used Scheme as the language--which is not hugely popular outside of GNU Guile, but works well for an intro course, even if students have had an into course w/ an OOP language like Java. As there may be undergrad, self-learners, and non-CS grad students checking out this article, here is a bit more information for consideration (it's true--there are other programming languages out there besides C++, Java, JavaScript and Python).

I can vouch that HtDP is what it goes by (just like SICP. I believe that it is a 'feature' of the people who write such things to just use acronyms for everything, and I don't know that there is much help for them...

To go with the book they have an open source didactic IDE [[2]] which is available for Windows, MacOS, and Linux (released as self-installing script or as an Ubuntu PPA, and it is available from Flathub and the Snap Store, that gradually exposes students to the full semantics and pragmatics of (open source Lisp/Scheme dialect) Racket, which the same group of authors is responsible for. There is also a similar book and IDE that uses Java designed for a second semester course on Data Structures and Algorithms. DrKC MD (talk) 02:53, 21 September 2023 (UTC)

Definition

The lead of this article has some problems. The article begins:

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

This is incorrect in two ways:

• Recursion is not "method of solving a problem". It is a programming construct. The same algorithm (method) can be expressed with or without recursion. After all, many problems solved with a recursive program can also be solved with a transparently equivalent iterative program (tail recursion). As Tony Hoare pointed out in his seminal article on Quicksort (1961), the recursive formulation makes it much more straightforward to express the logic of Quicksort, and to understand how it operates, but the algorithm (the method of solving the problem) is the same.
• In recursion, the solution does not necessarily "depend on solutions to smaller instances". The following is a perfectly valid recursive Python program for finding the Collatz conjecture step count:

def collatz(n):					   
  if n==1:						   
    return 0					   
  else:
    return 1 + collatz(n//2 if n%2==0 else 3*n+1)

If the Collatz conjecture is correct, then you could define the "smallness" of the problem instance as the step count of the number. If it is not, the function doesn't terminate for all values of n, but it is still a recursive function (just one that doesn't terminate in some cases -- just like the iterative equivalent). Here, again, the program could perfectly well have been written iteratively, but it is the form of the program, not the "method of solution", which is "recursive".

The next sentence is just mystifying:

Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time.

I have a Ph.D. in computer science, but I have no idea what this is supposed to mean. Of course all problems can be solved using iteration rather than recursion. But what on earth does "needs to identify and index the smaller instances at programming time" mean? I'll wait a few days for discussion before rewriting the lead. --Macrakis (talk) 21:30, 6 January 2021 (UTC)

I have no opinion about your first reason (method vs. construct).

I agree with your second reason (smaller vs. arbitrary). However, I think in the lead we should confine ourselves to the case of "smaller" subproblems (I'd prefer "simpler" to indicate this is a programmer-defined measure, not just size), since it conveys the main idea of recursion. Below in the article, subtleties like your collatz example can be discussed (maybe in a section "Defining partial functions by recursion" ?). Maybe, even a theorem to characterize the set of inputs on which a recursively-implemented function is defined (in the sense of "not diverging") can be stated there.

Finally, I agree that the sentence about iteration is incomprehensible at best. It should be replaced by a sentence which appropriately summarizes the section "Recursion#Recursion versus iteration". - Jochen Burghardt (talk) 15:34, 10 January 2021 (UTC)

Poor grammar in opening

The following is an awkward sentence; I fixed it but my edits have been revoked:

“Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time.”

It’s ok (but not great) that the first verb is passive because we don’t need to know *who* solves problems by iteration. But when writing in passive voice, you can’t just switch to active voice (“needs to identify”) and refer to the subject as “this”; the subject was deliberately omitted. I believe “this” refers to “a program making use of iteration”, and not just “iteration” or “such problems” (which is what the grammar badly implies).

To put this more simply: make sure the sentence says WHAT needs to i.d. and index…when (non-recursive) programs solve via iteration. Benlc (talk) 00:59, 6 March 2022 (UTC)

This was a terrible sentence for multiple reasons:

• all problems that can be solved recursively can be solved without recursion; it suffices to maintain a push-down stack;
• "identify and index" isn't intelligible English;
• "at programming time" makes no sense;
• whatever the point is, it probably doesn't belong in the lead.

I have removed the sentence. --Macrakis (talk) 02:53, 6 March 2022 (UTC)

PS I have been a Lisp programmer since 1967 and appreciate recursion quite deeply. --Macrakis (talk) 02:56, 6 March 2022 (UTC)

"Recursion(computer science)" listed at Redirects for discussion

The redirect Recursion(computer science) has been listed at redirects for discussion to determine whether its use and function meets the redirect guidelines. Readers of this page are welcome to comment on this redirect at Wikipedia:Redirects for discussion/Log/2023 June 2 § Recursion(computer science) until a consensus is reached. Steel1943 (talk) 21:25, 2 June 2023 (UTC)

This article presents a narrow view of recursion in computer science

This article focuses on recursion in computer programming, and does not cover other uses of recursion in computer science, for example in databases and knowledge representation. It focuses on recursive functions and ignores recursive relations. See, for example, the recursive definition of the ancestor relation in the Datalog article.

Moreover, because of its focus on programming, the article limits problem solving and execution methods to backward chaining, and it ignores forward chaining.

More importantly, it does not distinguish between recursive structure and the way in which that structure is used to solve problems. It fails to point out that pure recursion can be understood declaratively, without understanding execution at all. Consider, for example, the Prolog program, which expresses that alice likes logic, and that she likes anything that likes logic:

likes(alice, logic).
likes(alice, X) :- likes(X, logic).

Robert Kowalski (talk) 12:31, 6 March 2024 (UTC)