Prelude to Computer Science: Recursion Hints

Recursion can be a useful tool, if you understand how it works. Expect recursive techniques to use more memory and execution time than comparable sequential/iterative techniques. Watch your depth!

1. Review "parameter passing" in whatever textbook you're using. (in particular make sure you understand the difference between passing by value and passing by reference)
2. Review the pages in your book that discuss "storage class" (static vs dynamic memory)
3. Solve your problem on paper first just using symbols and lines.
4. Check your TERMINATION and RECURSIVE CONDITIONS. Recursion requires 2 things: a recursive rule(s) and a termination condition!
5. Solve the simplest version of the program that you can think of first, i.e. factorial(0) or generate a fractal one level deep.

Category:

Science & Technology

Tags:

• prelude
• computer
• science
• introduction
• recursion
• hints
• storage
• class
• parameter
• argument
• passing
• progamming

[anforhell69]

Which book, you refered?

[TheFallibleFiend]

No specific book. I'm assuming that the person watching this is taking a class that is using a book to cover the basics of some computer language. Regardless of the the particular book, there should be a part in it that talks about the method used to pass arguments to functions: reference, value, etc. The book should have some detail about what each of those methods means. Good to understand that before attempting recursion.

[Tiwaking]

There were some excellent points that are not addressed in Computer Science textbooks such as "Pass by value in Java can sometimes look like pass by reference". Also: Great example of the theoretical use of recursion

[TheFallibleFiend]

tx for feedback,

tff

[isilder]

recursion is useful for handling the case where the data structure for a sequentional, iterative style is hard.

It even avoids the need for having access to memory allocation function calls.

Of course, a stack data structure can do the same as any recursive algorithm, since recursion just makes a data structure on the cpu's stack !

[TheFallibleFiend]

Good point. Recursion is very good for graph (including tree or linked list) traversal. Also good to hone understanding of scope, storage class, & parameter passing. Implementing with stack is a good way to hone understanding of details of how recursion works. I agree with teaching recursion to intro students, but disagree with testing them on it.

[epicswell]

Thanks sir, some great pieces of advice there. Pen and paper first then so...

[daambassador1]

thanks bud -- good insight ;)

[Ganjin88]

I believe your right. My professor this summer talk about it for less than 2 minutes. And guess what? She put it on the last exam we had last week. Plenty of student had 60's and 50's. In my opinion, I dont think it was a fair test because the book never had anything on recursive functions and she only talked about it for approximately 2 minutes.

:(