AP Computer Science ppl...what's recursion?

[dude8604]

The APCS book my teacher is using is really bad, and I really don't get recursion. FYI the book is C++ How To Program by Dietel and Dietel. Can someone explain it to me. Also, what APCS books do you use? Thanks.

 

[tweakmm]

a good metaphor is a snake eating its tail


it's a joke that was going around in my AP Computer Science class

 

[spp]

it's just a function that calls itself

 

[Noriaki]

I have no idea what AP means...

But recursion is a concept where something is defined in terms of itself.


For example...

f(0) = 1
f(1) = 1
f(n) = f(n-1) + f(n-2) for all n >= 2

You have base cases, that tell you how to construct the simplest items in the set.
Then you have a recursive or inductive defintion whereby given 1 or more items already in the set, you construct a new one.

In this case (the fibonacci numbers) the first 2 numbers are 1, and any after the 3rd is the sum of the previous two.

Another easy example is factorial
Here's a C function for recursive factorial.

int fact(int n) {
if (n == 1) return 1;
else return n * fact(n-1);
}

It has a simple base case (n == 1) and then more complex factorials call the function itself to compute them.

Edit:
This factorial function is not very safe....it only works when the initial call is >= 1...but that's okay...it still demonstrates alright.

 

[Hooligan]

your return if you do return anything is a function call to the function

 

[tweakmm]

http://www.cprogramming.com/tutorial/lesson16.html
it makes sense to me(although I already understand the concepts of recusion)
maybe it'll help you out

 

[KingNothing]

Originally posted by: tweakmm
a snake eating its tail


it's a joke that was going around in my AP Computer Science class

The TOOL concert I went to was awesome! If...that's what you're talking about. :-D

As for what recursion is, it's where a function calls itself until a terminating condition is reached. Like so:

int recursive_function(int x)
{
if (x > 0)
{
x--;
x = recursive_function(x);
}
return x;
}

Someone smarter than me tell me if that works, I suck at writing recursive code. That's the general idea of recursion though.

BTW, the Deitel book SUCKS, IMO. Return it and get yourself something from a real bookstore.

 

[trmiv]

Uh oh, I feel the Towers of Hanoi coming on

 

[KingNothing]

BTW, AP = Advanced Placement. You take courses in high school that are harder than normal courses and in return you get college credit.

 

[michaelh20]

CS book people love those obtuse (spelling?) examples.....

Here's a more straight forward example:

(This is Java BTW)

A File is an object representing a file, directory or normal file on an OS.
To get the size of a bunch of files:

(1) If the bunch of files is just empty we return 0
(2) If not an empty bunch of files then we cycle through all the files
and addup the size of each normal file. If there is a directory, then we call
getSize (the same function) on the listing of all the files in that directory and add that size to the total size.

Note that in recursion, there is usually the function calling itself, but there should always be a stopping condition, where the looping terminates, in this case it's when the fileset is empty.

/**
* Get the size of a number of local files and dirs, recursively.
* Does not check for loops
*/
public long getSize(File[] files){
if (files ==null || files.length == 0) return 0;


long returnMe = 0;

for (int i = 0; i < files.length; i ++){
if (files.isDirectory()){
returnMe += getSize(files.listFiles());
}
else{
returnMe+=files.length();
}
}
return returnMe;
}

 

[white]

granted, i suck at programming, but check out this thread.


recursion

 

[michaelh20]

>> Uh oh, I feel the Towers of Hanoi coming on


Run away! Run Away!

<-- ponders moments of boredom on the verge of falling asleep during ponderous hardly understood proofs

 

[Rahminator]

Here's a programmer's dictionary definition:

recursion (v.) - see recursion.

 

[singh]

If you want to understand recursion, then read a simple snippette of code follow along on a piece of paper.