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

#### dude8604

##### Platinum Member
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

##### Lifer
a good metaphor is a snake eating its tail

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

#### spp

##### Golden Member
it's just a function that calls itself

#### Noriaki

##### Lifer
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

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

#### KingNothing

##### Diamond Member
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

##### Lifer
Uh oh, I feel the Towers of Hanoi coming on

#### KingNothing

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

#### michaelh20

##### Senior member
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

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

recursion

#### michaelh20

##### Senior member
>> 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

##### Senior member
Here's a programmer's dictionary definition:

recursion (v.) - see recursion.

#### singh

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

Replies
19
Views
5K
Replies
33
Views
1K
Replies
8
Views
840
Replies
367
Views
12K
Replies
11
Views
4K