Properly reading recursive functions

Question

I currently teach myself programming and I came to a point where I was introduced to the recursive functions. I understand the basic principle behind them but whenever I try to read a code which contains recursive functions I have tough times tracing them. Honestly, If I don't write down the whole function on a paper and manually follow it I can't really understand what it does, I can't follow it mentally is what I am saying. Can you give some tips on how to do it mentally? I am pretty much average intelligent ( IQ 117 ), maybe that's the problem? Thanks in advance.

Recursion is a terrible tool that is used significantly too often. — DwB, Mar 08 '17 at 19:20
Voting to reopen. This is a valid question on how best to understand recursion. Although answers will be based somewhat on empirical knowledge, that is often the case and does not invalidate the question. — rghome, Mar 15 '17 at 12:55

score 0 · Answer 1 · edited May 23 '17 at 12:17

0

I think IQ does not matter. Anyway, i think it's all about practice. Try to write some recursive functions. And after alot of practice and experience you will find it more easy to understand.

There is some good ideas. Good luck.

edited May 23 '17 at 12:17

Community

1
1

answered Mar 08 '17 at 16:18

Maksym Bodnar

125
8

score 0 · Accepted Answer · answered Mar 08 '17 at 20:16

I think this is an excellent question. Many people make the mistake of trying to follow the call-stack of a recursive function, which is the wrong approach.

I find the only way is to look at what is written and ask yourself whether it is logically correct and whether it will end. If those things are true, it is going to work and you don't really need to understand how.

In more detail:

Are all possible input values considered?
Are the statements true in each case?
Is there a (are there) value(s) at which point the function will not recurse?
Do all remaining input values ultimately lead to that value?

For example (pseudo code):

factorial(n):
    if (n < 0) throw InvalidArgument
    if (n == 0) return 1
    else return factorial(n - 1) * n

All input values are covered. The statements are true. There is a value at which it does not recurse (<=0) and the all remaining values reduce by 1 until the exit value is reached. Therefore it works.

You may of course make mistakes in your thinking. A good IQ does help here, and you may need at some point to resort to tracing or debugging to check your assumptions and find the error in your logic, but this should not be the first approach.

That is the beauty of recursive solutions: they tend to be statements of fact rather than procedural instructions!

Thank you, sir. So, essentially, I am not that stupid, I was just using the wrong approach, right? — Eddie Spasov, Mar 15 '17 at 11:52
Yes - indeed! The intelligent thing to do in this case is to understand the fundamental correctness of the algorithm, not try and trace every execution path. Please upvote the answer as well if you think it is valuable. — rghome, Mar 15 '17 at 12:54

Properly reading recursive functions

2 Answers2