# Recursion

Page 1 of 1

## 9 Replies - 2539 Views - Last Post: 08 October 2001 - 05:18 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=2462&amp;s=012477026c730bdf55c62c47fb5db308&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 nighthawk

• D.I.C Lover

Reputation: 0
• Posts: 1,269
• Joined: 11-April 01

# Recursion

Posted 02 October 2001 - 08:44 AM

I'm presently learning about recursion in my CS class and the way that my teacher introduced it to us was with the fibonacci numbers (which are cool from a mathematical perspective)

well first he said that recursion was calling the same function that you're in with in that function

this is how he showed it to us:

```/* Fibonacci sequence by recursion: this is inefficient
since it calculates the same values many times. */#include <iostream.h>int main() {
int i;
cout << "F(i) for what i? " << endl;   //asks which number in the sequence you want
cin >> i;  //gets that number
fib(i);   //takes it to the function to calculate that number
return 0;
}//calculates the number in the sequence that was asked for
int fib(int i) {
if (i==0 || i==1) return 1;
else return fib(i-1) + fib(i-2);  //this is the line of recursion: fib(i-1) + fib(i-2) the function is calling it's self.
}

```

just thought that i would share what i'm learning in class, hope that someone finds it interesting :)

Is This A Good Question/Topic? 0

## Replies To: Recursion

### #2 malkiri

• D.I.C Regular

Reputation: 3
• Posts: 364
• Joined: 29-March 01

## Re: Recursion

Posted 02 October 2001 - 10:38 AM

Recursion r0x0rz. Using it in C++ makes me feel queasy though...if you're really interested in it, take a look at some functional languages like LISP or MIT Scheme. That's where I learned my recursion from. Of course, recursion is recursion...but I found it to be more fun in Scheme. :)

-Malkiri

(edit: oops, it's functional, not procedural :) )

(Edited by malkiri at 8:59 am on Oct. 2, 2001)

### #3 nighthawk

• D.I.C Lover

Reputation: 0
• Posts: 1,269
• Joined: 11-April 01

## Re: Recursion

Posted 02 October 2001 - 10:51 AM

i've never heard of LISP or MIT scheme, care to expand on those?

### #4 malkiri

• D.I.C Regular

Reputation: 3
• Posts: 364
• Joined: 29-March 01

## Re: Recursion

Posted 02 October 2001 - 11:03 AM

Well, it's been a few years since I've used Scheme, so I hesitate to try to give you my own description of them. Instead, check out this page. It has a pretty good description of LISP and its family.
http://www.elwoodcor.../table/lisp.htm
Just to warn you...it's very different from C/C++ and the like, so wait 30 minutes after eating and chew throughly.

-Malkiri

### #5 supersloth

• serial frotteur - RUDEST MEMBER ON D.I.C.

Reputation: 4665
• Posts: 28,487
• Joined: 21-March 01

## Re: Recursion

Posted 02 October 2001 - 02:48 PM

recursion, is awesome. im only on the beginners level of it, but its just powerful as ####.

### #6 nighthawk

• D.I.C Lover

Reputation: 0
• Posts: 1,269
• Joined: 11-April 01

## Re: Recursion

Posted 04 October 2001 - 09:54 AM

i'm only a beginner also...my next program will be connect 4 player vs. computer and i have to use recursion...it kind of scares me...

### #7 malkiri

• D.I.C Regular

Reputation: 3
• Posts: 364
• Joined: 29-March 01

## Re: Recursion

Posted 04 October 2001 - 10:33 AM

Do you mean that the assignment requires you to use recursion, or that there is some part of the program that needs recursion? I ask because though recursion is very powerful, it's not usually the best way to do things, especially in C++.

-Malkiri

### #8 runtime error

• Lucky.Code

Reputation: 3
• Posts: 629
• Joined: 19-March 01

## Re: Recursion

Posted 04 October 2001 - 12:31 PM

Quote

Quote: from malkiri on 1:33 pm on Oct. 4, 2001
Do you mean that the assignment requires you to use recursion, or that there is some part of the program that needs recursion? I ask because though recursion is very powerful, it's not usually the best way to do things, especially in C++.

-Malkiri

What he said.:yes:

I know recursion i just never found a use for it. Except for maybe finding a factorial of a number.

### #9 malkiri

• D.I.C Regular

Reputation: 3
• Posts: 364
• Joined: 29-March 01

## Re: Recursion

Posted 04 October 2001 - 01:41 PM

Even factorials can be computed iteratively:
```// Compute factorial of f
int f = 10;
int fact = 1;
for (int i = f; i>1; i--)
{
fact *= i;
}

```

Now, I'm not trying to play down recursion...I love it. You just have to be working in something that can handle it well.

On a semi-side note, try to code a program to solve this classic problem (without cheating :p):
Given a standard chess board (8 squares by 8 squares), in how many ways is it possible to arrange eight queens such that no queen can capture any of the seven others? For a slightly greater challenge, only count symetrical arrangements once (that is, the board is mirrored or rotated to produce a "different" arrangement).

For example, here is one of the arrangements, where * is a queen and - is an empty spot:

```*-------
----*---
-------*
-----*--
--*-----
------*-
-*------
---*----

```

-Malkiri

### #10 nighthawk

• D.I.C Lover

Reputation: 0
• Posts: 1,269
• Joined: 11-April 01

## Re: Recursion

Posted 08 October 2001 - 05:18 AM

funny that you should bring up the classic puzzle of queens, we just went over it in class...not sure that i completely understand everything that my prof told us, but i'm sure he made it harder than it really is...he used classes and whatnot...