CODEWITHSUNDEEP
javarecursion
brld
brld

Reputation: 188

Recursion clarification

I just wanted to make sure that I was completely solid on recursion. I have used it in a bunch of applications, but realized that when someone asked me to define it (a newer programmer asked this), I was a bit shaky on the definition and had a bit of trouble explaining it. I just wanted to reach out to a large programming community to make sure I was on the right track.

From what I know, recursion in computer science is when some answers to a given problem or check (i.e. an if statement) depend on something else related to the same method. A way to solve this could be a function calling on itself (which the majority of programming languages support). I wrote a simple Fibonacci program below:

public int fib(int n) {
    if(n <= 1) {
        return n;
    } else {
        return fib(n - 1) + fib(n - 2);
    }
}

Let me know if I'm on the right track. Also, I am aware that there are similar questions on recursion, but please do not close this question as a duplicate because this is a more general question not limited to a specific language, but more a concept on what recursion is.

Thanks,

brld

Upvotes: 0

Views: 102

Answers (1)

Prune
Prune

Reputation: 77910

You're on the right track. I would break this up into pieces:

  1. Definition: By dictionary definition, recursion is a a process calling itself. This call is usually direct, as in your example, but can also be indirect: f1 and f2 call each other, but not themselves.
  2. Example: Just as you did ... show a well-known function with an easily understood recursive definition. I usually use factorial, since it has only one recursive call; then I present the Fibonacci case.
  3. Mechanics: Describe the critical properties of base case (what makes it stop, at last) and simplification (reduce the problem before you recur).
  4. Proper use: Pretty much any real programming application with a recursive description will have an iterative (looping) solution that takes less computing time. However, if the natural description is recursive, it's quite possible that the most efficient solution in the long run is recursive. Consider repair and maintenance resources in addition to mere execution cycles, and remember that FLOPS get cheaper every month.

Upvotes: 2

Related Questions