9 Replies - 2208 Views - Last Post: 08 October 2001 - 05:18 AM Rate Topic: -----

#1 nighthawk  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • 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  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 3
  • View blog
  • 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)

Was This Post Helpful? 0
  • +
  • -

#3 nighthawk  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • 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?
Was This Post Helpful? 0
  • +
  • -

#4 malkiri  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 3
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#5 supersloth  Icon User is offline

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


Reputation: 4517
  • View blog
  • Posts: 28,417
  • 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 ####.
Was This Post Helpful? 0
  • +
  • -

#6 nighthawk  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • 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...
Was This Post Helpful? 0
  • +
  • -

#7 malkiri  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 3
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#8 runtime error  Icon User is offline

  • Lucky.Code
  • member icon

Reputation: 3
  • View blog
  • 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.

Was This Post Helpful? 0
  • +
  • -

#9 malkiri  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 3
  • View blog
  • 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

Was This Post Helpful? 0
  • +
  • -

#10 nighthawk  Icon User is offline

  • D.I.C Lover

Reputation: 0
  • View blog
  • 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...
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1