Three characteristics of recursive programs

Question

I needed to look up about the three major characteristics of recursive programs and I found Single recursion & multiple recursion, Indirect recursion and Anonymous recursion. That was the first research I done. I have recently found linear, tail and binary instead.

The question is, are the first set of characteristics correct or is the second list? What I am thinking is, the first three I found are the characteristics and the second lot I found are the types of recession.

What is correct here?

Please note:

This is not a duplicate of What is recursion and when should I use it? since none of the terms such as linear and Indirect recursion are mentioned in there.

To me those look type types of recursion vice characteristics - like breaking the problem into smaller pieces, having an end/stop state, etc — eze, Jun 14 '16 at 16:37
@JonHarper This is not asking what recursion is, instead it is what the characteristics of it is. I don't see any of the terms that I have in my question in the answers of the 'duplicate question' — iProgram, Jun 14 '16 at 16:44
I want to check the premise of this: why do you need to look up characteristics? Who says there are exactly three? — Prune, Jun 14 '16 at 18:09
@Prune Just needed to do it for a task (I need to explain them too, meaning I cannot answer the question if people just list the characteristics). I have not said that it is exactly three. Also, I have only asked if it is correct. I did not ask for any detail or what they were. The main part of task is researching, the answers here have only gave me pointers in the right direction. (If this sounds like I am being rude, I am not. Sorry if it was taken this way [I can understand why you could]) — iProgram, Jun 14 '16 at 19:05
@iProgram, I do not read this as rude at all. I want to make sure we (eventually) give you the help you need, so I asked for the background of the problem. Thank you for the clarification. — Prune, Jun 14 '16 at 20:46

score 1 · Accepted Answer · answered Jun 14 '16 at 18:12

1

What you've listed in your question are types of recursion, not characteristics. I'm going to venture in another direction. I would list

test for base case
base action (no recursive call)
non-case action (at least one recursive call)

Another possibility is that every recursive call moves closer to the base case, "closer" being in the sense of graph distance.

answered Jun 14 '16 at 18:12

Prune

76,765
14
60
81

Your first two bullets look like the same thing to me. – pjs Jun 14 '16 at 18:16
One is identification; the other is (non-recursive) action. I like your first bullet better. – Prune Jun 14 '16 at 18:31
Thank you for your answer. With more research that I done, I was able to complete the task and I also got the grade I wanted. Would give you some bounty but cannot find out how to. – iProgram Jun 16 '16 at 09:07
Glad to be of help. Other than up-voting the answer and accepting it, there's nothing else to do -- you gave me a smile to start the day. I have enough points. However, you *could* edit an answer to include the research you did -- this gives a more complete answer for future SO citizens, which is the main purpose of the group. – Prune Jun 16 '16 at 15:53

score 1 · Answer 2 · answered Jun 14 '16 at 18:27

You've identified different types of recursion, but haven't addressed what they all have in common:

the solution to the problem can be expressed as a function of one or more identically structured sub-problems, i.e., the solution will potentially involve other calls to the same function but with different parameterization;
there exist one or more "base cases" with known solutions;
the sequence of recursive calls must converge to a base case in a finite number of calls.

That last one isn't required for mathematical recursion, but is needed for computational recursion.

Three characteristics of recursive programs

2 Answers2