[nighthawk]

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 :)

[malkiri]

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)

[nighthawk]

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

[malkiri]

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

[supersloth]

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

[nighthawk]

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...

[malkiri]

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

[runtime error]

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.

[malkiri]

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

[nighthawk]

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...