# I'm learning to code (again)!

**URL:** <https://boards.straightdope.com/t/im-learning-to-code-again/334411>\
**Category:** Miscellaneous and Personal Stuff I Must Share\
**Created:** [December 6, 2005, 9:19pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411 "2005-12-06T21:19:13Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Electronic\_Chaos](https://avatars.discourse-cdn.com/v4/letter/e/bbe5ce/32.png) [@Electronic\_Chaos](https://boards.straightdope.com/u/Electronic_Chaos)\
**Post date:** [December 6, 2005, 9:19pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/1 "2005-12-06T21:19:13Z")

</div>

Every now and then I get bored and pick up my C++ book, and relearn the basics, and teach myself new things. It seems I don’t have the attention span to learn the whole thing at once. I was surprised by how much actually has stuck, though.

Like for example, I was able to make a guess the number game where the computer picks a random integer, and the player has to guess what it is, while the computer tells you if it’s too high or two low. I did this on a whim the first day I decided to pick it back up, and it took about 20 minutes. I was so proud I showed it to all my friends 😃 .

I just finished a program that would calculate how many quarters, dimes, nickels, and pennies are in a user-given monetary amount.

I’ve also made a program that makes sequentially bigger rows of asterisks, up to a given amount. And a variation on that, where the rows get bigger, then smaller.

So, coding-dopers, how about you give me some problems which can be solved with my limited knowledge.

So far I know how to use:  
-if statements  
-for, while, and do-while loops  
-void, and return functions  
-switch statements

I think that’s it for now, but I welcome all challenges, no matter the difficulty.

Alternatively, if you would like to see my programs (either the source code, the compiled version, or both), you can email me!

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 6, 2005, 9:52pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/2 "2005-12-06T21:52:03Z")

</div>

> [@Electronic Chaos](#):
>
> So, coding-dopers, how about you give me some problems which can be solved with my limited knowledge.

[These should keep you busy.](http://acm.uva.es/problemset/)

---

<div class="post-metadata">

**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\
**Post date:** [December 7, 2005, 12:52am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/3 "2005-12-07T00:52:56Z")

</div>

Do you know how to write recursive programs?

Try writing one that takes in a number n and returns the nth Fibonacci number.

For reference, F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2);

Once you learn recursion, you can learn dynamic programming, which is a really awesome programming technique that can help you find an optimal solution to lots of tricky problems.

---

<div class="post-metadata">

**Author:** ![Electronic\_Chaos](https://avatars.discourse-cdn.com/v4/letter/e/bbe5ce/32.png) [@Electronic\_Chaos](https://boards.straightdope.com/u/Electronic_Chaos)\
**Post date:** [December 7, 2005, 1:10am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/4 "2005-12-07T01:10:59Z")

</div>

> [@iamthewalrus(:3=](#):
>
> Do you know how to write recursive programs?
> 
> Try writing one that takes in a number n and returns the nth Fibonacci number.
> 
> For reference, F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2);
> 
> Once you learn recursion, you can learn dynamic programming, which is a really awesome programming technique that can help you find an optimal solution to lots of tricky problems.

You mean like this?:

```auto

int main(){

	int limit;
	int a;
	int b;
	int c;
	int count;

	cout << "Please enter limit: ";
	cin >> limit;
	cout << endl;

	a = 0;
	b = 1;
	
	for (count = 1; count <= limit; count++){
		cout << b << " ";
		c = b;
		b = a + b;
		a = c;
		}
	
	return 0;
	}

```

---

<div class="post-metadata">

**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\
**Post date:** [December 7, 2005, 1:31am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/5 "2005-12-07T01:31:09Z")

</div>

Well, yes, that works. But it’s not recursion. My fault: I didn’t explain. A recursive program is one that calls itself. If you’ve ever written an inductive proof, it’s a similar sort of concept.

Can you write a function fib(int n) that returns the nth fibonacci number, and to do so, doesn’t run a for loop and add it up, but calls _itself_ again?

---

<div class="post-metadata">

**Author:** ![Electronic\_Chaos](https://avatars.discourse-cdn.com/v4/letter/e/bbe5ce/32.png) [@Electronic\_Chaos](https://boards.straightdope.com/u/Electronic_Chaos)\
**Post date:** [December 7, 2005, 6:36am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/6 "2005-12-07T06:36:15Z")

</div>

> [@iamthewalrus(:3=](#):
>
> Well, yes, that works. But it’s not recursion. My fault: I didn’t explain. A recursive program is one that calls itself. If you’ve ever written an inductive proof, it’s a similar sort of concept.
> 
> Can you write a function fib(int n) that returns the nth fibonacci number, and to do so, doesn’t run a for loop and add it up, but calls _itself_ again?

Ah, now I see. So it’d be like this:

```auto

int fib(int limit){

	c = b;
	b = a + b;
	a = c;
	count++;
	cout << b << " ";
	
	if(count >= limit){
		return 0;
		}
	else{
		fib(limit);
		}
}

```

---

<div class="post-metadata">

**Author:** ![iamthewalrus\_3](https://avatars.discourse-cdn.com/v4/letter/i/258eb7/32.png) [@iamthewalrus\_3](https://boards.straightdope.com/u/iamthewalrus_3)\
**Post date:** [December 7, 2005, 7:09am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/7 "2005-12-07T07:09:53Z")

</div>

That’s partway there **Electronic Chaos** (and technically is everything I described). You’ve removed the for loop and replaced it with recursive calls. To make the function completely recursive, though, you should not rely on any external (global) variables. You can do that by removing the variables and using the arguments of the function itself to pass the information you need.

To illustrate my point, here’s an example recursive function that adds two numbers together

```auto

int sum(x, y) {
    if (y == 0)
        return x;
    else
        return sum(x+1, y-1);
}

```

Now, obviously, that’s a really stupid way to add numbers. And in this case only works if y \> 0 to start. But the idea is that you let further function calls do the heavy lifting and don’t store extra information in external variables.

---

<div class="post-metadata">

**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\
**Post date:** [December 7, 2005, 10:01am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/8 "2005-12-07T10:01:49Z")

</div>

Gah, I don’t know why people insist on using fibonacci to demonstrate recursion. Nobody but a braindead monkey would EVER write fibonacci the pure recursive manner due to it being godawful slow (assuming your not programming in a pure functional language :D). There are so much better examples to demonstrate recursion to a beginner.

---

<div class="post-metadata">

**Author:** ![Small\_Clanger](https://avatars.discourse-cdn.com/v4/letter/s/9fc348/32.png) [@Small\_Clanger](https://boards.straightdope.com/u/Small_Clanger)\
**Post date:** [December 7, 2005, 10:49am UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/9 "2005-12-07T10:49:35Z")

</div>

> [@Electronic Chaos](#):
>
> So, coding-dopers, how about you give me some problems which can be solved with my limited knowledge

The problems I looked at in **UncleRojelio** ’s link looked scary.

> [@](#):
>
> -if statements  
> -for, while, and do-while loops  
> -void, and return functions  
> -switch statements

Add some knowledge of arrays (which is essential) this should be enough to write a Sudoku puzzle solver.

You’ll probably want learn how to read and write files, you don’t want to be entering all your Sudoku data at the console.

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 7, 2005, 2:52pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/10 "2005-12-07T14:52:09Z")

</div>

> [@Shalmanese](#):
>
> Gah, I don’t know why people insist on using fibonacci to demonstrate recursion. Nobody but a braindead monkey would EVER write fibonacci the pure recursive manner due to it being godawful slow (assuming your not programming in a pure functional language :D). There are so much better examples to demonstrate recursion to a beginner.

I’s kinda like the “Hello World” of recursion. Just roll with it.

> [@](#):
>
> The problems I looked at in UncleRojelio’s link looked scary.

The really scary part is when you sumbit them and the robot emails back that you are WRONG!!!.

**Electronic Chaos** , the other central part of recursion, besides the fact that the function calls itself, is that the problem gets smaller upon each recursion. Take for (cannonical) example; Factorial. You could simply define:

```php

n! = 1 * 2 * ... * n

```

but a better and recursive why to think of it is:

```php

0! = 1 // base case
n! = n * (n-1)! // general case

```

Now, you can imagine a function that calls itself repeatedly as the value of n decreases. Upon reaching the base case, the function returns as begins unstacking the previous calls until the original call returns with the answer.

Recursion is one of those portals through which all programers must pass. It is very important to be able to wrap your head around this concept for it leads to the Holy Grail of computer science; Funtional Programming.

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 7, 2005, 3:26pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/11 "2005-12-07T15:26:52Z")

</div>

Yike, as fun as programming is, that last line should have read: Fun **c** tional Programming.

I would like to recommend this [book](http://www.bookpool.com/sm/0201350882) for your programming pleasure. Chock full of fun and interesting programming challenges.

---

<div class="post-metadata">

**Author:** ![Shalmanese](https://avatars.discourse-cdn.com/v4/letter/s/45deac/32.png) [@Shalmanese](https://boards.straightdope.com/u/Shalmanese)\
**Post date:** [December 7, 2005, 3:51pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/12 "2005-12-07T15:51:59Z")

</div>

> [@UncleRojelio](#):
>
> I’s kinda like the “Hello World” of recursion. Just roll with it.

I prefer to think of it as the “Bubble Sort” of recursion.

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 7, 2005, 3:58pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/13 "2005-12-07T15:58:31Z")

</div>

> [@Shalmanese](#):
>
> I prefer to think of it as the “Bubble Sort” of recursion.

I had the same prof for three different CS courses. Programming, Algorithms, and Data Structures. He managed to shoehorn old Fibonacci into every class one way or another.

That and Haskell. One way or another.

---

<div class="post-metadata">

**Author:** ![Crowbar\_of\_Irony\_3](https://avatars.discourse-cdn.com/v4/letter/c/f08c70/32.png) [@Crowbar\_of\_Irony\_3](https://boards.straightdope.com/u/Crowbar_of_Irony_3)\
**Post date:** [December 7, 2005, 4:27pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/14 "2005-12-07T16:27:08Z")

</div>

Hmm…the toughest thing I ever done is a path-finding program, using recurison. You need an array for that. So the project spec is:

1. Define a maze given a 2d array
2. Define a start point
3. Define an end point
4. Trace a route from the start to end

Actually, given what you know, and some array basics, you can do all sort of nifty stuff…

1. An ASCII calendar.
2. A Trek game! You command a starship (think Enterprise) and have to elminate all the enemies from the galaxy. Galaxy is divided in 8x8 quadrants, and each quadrant has starbases, black holes, stars and etc.

---

<div class="post-metadata">

**Author:** ![friedo](https://avatars.discourse-cdn.com/v4/letter/f/8edcca/32.png) [@friedo](https://boards.straightdope.com/u/friedo)\
**Post date:** [December 7, 2005, 4:29pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/15 "2005-12-07T16:29:41Z")

</div>

Now that you know about recursion, **Electronic Chaos** , learn about [binary trees](http://en.wikipedia.org/wiki/Binary_tree) and write a recursive function that will traverse a binary tree and output the data of each node.

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 7, 2005, 4:37pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/16 "2005-12-07T16:37:26Z")

</div>

> [@ExtraKun](#):
>
> 1. A Trek game! You command a starship (think Enterprise) and have to elminate all the enemies from the galaxy. Galaxy is divided in 8x8 quadrants, and each quadrant has starbases, black holes, stars and etc.

I work with a guy that wrote part of a version at the University of Texas. Their version was written in Fortran, and the printed source resulted in a three inch thick stack of pin-feed computer paper. No telling how tall the stack of computer punch cards used to enter the source into the mainframe was. I used to play it in high school on a teletype machine hooked to an acoustic modem. Those were the days.

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 7, 2005, 4:39pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/17 "2005-12-07T16:39:44Z")

</div>

> [@friedo](#):
>
> Now that you know about recursion, **Electronic Chaos** , learn about [binary trees](http://en.wikipedia.org/wiki/Binary_tree) and write a recursive function that will traverse a binary tree and output the data of each node.

When you want to write a level-order search, let us know, we’ll let you in on the secret.

---

<div class="post-metadata">

**Author:** ![Crowbar\_of\_Irony\_3](https://avatars.discourse-cdn.com/v4/letter/c/f08c70/32.png) [@Crowbar\_of\_Irony\_3](https://boards.straightdope.com/u/Crowbar_of_Irony_3)\
**Post date:** [December 7, 2005, 4:40pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/18 "2005-12-07T16:40:03Z")

</div>

> [@friedo](#):
>
> Now that you know about recursion, **Electronic Chaos** , learn about [binary trees](http://en.wikipedia.org/wiki/Binary_tree) and write a recursive function that will traverse a binary tree and output the data of each node.

After that you might want to look into Binary Search Trees:  
Obiligatory Wiki-Link: [http://en.wikipedia.org/wiki/Binary\_search\_tree](http://en.wikipedia.org/wiki/Binary_search_tree)

---

<div class="post-metadata">

**Author:** ![UncleRojelio](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/unclerojelio/32/3160_2.png) [@UncleRojelio](https://boards.straightdope.com/u/UncleRojelio)\
**Post date:** [December 7, 2005, 4:46pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/19 "2005-12-07T16:46:44Z")

</div>

> [@ExtraKun](#):
>
> After that you might want to look into Binary Search Trees:  
> Obiligatory Wiki-Link: [http://en.wikipedia.org/wiki/Binary\_search\_tree](http://en.wikipedia.org/wiki/Binary_search_tree)

Then you can compare and contrast that with the [Hash table](http://en.wikipedia.org/wiki/Hash_table).

---

<div class="post-metadata">

**Author:** ![Nature\_s\_Call](https://sea3.discourse-cdn.com/straightdope/user_avatar/boards.straightdope.com/nature_s_call/32/19006_2.png) [@Nature\_s\_Call](https://boards.straightdope.com/u/Nature_s_Call)\
**Post date:** [December 7, 2005, 5:17pm UTC](https://boards.straightdope.com/t/im-learning-to-code-again/334411/20 "2005-12-07T17:17:14Z")

</div>

When I taught C++, one textbook I used had this exercise

“Enter a height, program draws a diamond that wide using asterisks.”  
e.g. enter 5 you get:

```auto

  *
 ***
*****
 ***
  *

```

I almost dismissed this as too trivial, but there are soooo many ways to solve it, it became a great compare/contrast exercise when taken up as a group. And there are some gotchas.

* * *

I too consider Fibonacci to be the “Hello, world” of recursion not because recursion is the best way to do it but that the whole shebang is easy to grasp.

As a test for recursion I would assign the [Towers of Hanoi](http://www.cut-the-knot.org/recurrence/hanoi.shtml)  
Write a program that outputs the steps to solve the Towers of Hanoi (make the number of rings an input if you wish, or fix it at 4)

The output should look something like this  
“Move ring from tower 1 to tower 2”  
“Move ring from tower 1 to tower 3”  
“Move ring from tower 2 to tower 3”  
etc…

* * *

As for C++ - are you ready for object oriented exercises? The classic is:  
[ul]  
[li]Define a class named Shape that has an abstract method GetArea(), and DisplayCharacteristics()[/li][li]Inherit from Shape to define Circle, Rectangle, Triangle, Square, each overloading GetArea() and DisplayCharacteristics() as appropriate. e.g. DisplayCharacteristics() for the Circle could be **cout \<\< “A circle with " \<\< r \<\< " radius.” \<\< endl;** [/li][li]Display a menu offering the user to pick one of these four shapes, then to supply the defining coordinates of the chosen shape (radius for circle, base & height for the triangle, etc)[/li][li]Using the input, construct the appropriate shape and add it to an array of shapes.[/li][li]When user is done entering shapes, iterate the array displaying the characteristics and area of each Shape.[/li][/ul]

[Next page](https://boards.straightdope.com/t/im-learning-to-code-again/334411.md?page=2)