Non-Recursive function

program_help · #1 16-Jan-2010, 17:29

I don't understand the concept of non-recursive functions. If I am to write a non-recursive function, not using bitwise operations, to print out a non-negative number in binary, how would I do it?

I know that for the recursive function:

CPP / C++ / C Code:

void binaryEquivalent(int num, int base)
{
  if (num == 0)return;
  {
    binaryEquivalent(num/base, base);
    cout<< num % base; 	
  } 
}

I don't know if it is so basic that I am missing it, but I just can't seem to wrap my mind around doing it non-recursively. Any help would be greatly appreciated.

ocicat · #2 19-Jan-2010, 23:45

Quote:

Originally Posted by program_help

I don't understand the concept of non-recursive functions.

The first thing to do when confronted with new concepts & assignments which are fuzzy is to write simple throw-away code which exercises the fundamental concept. ie.

CPP / C++ / C Code:

#include <iostream>

using namespace std;

void binaryEquivalent(int, int);

int
main() {
  cout << "5 (base 2) = ";
  binaryEquivalent(5, 2);
  cout << endl;

  cout << "5 (base 8) = ";
  binaryEquivalent(5, 8);
  cout << endl;

  return 0;
}

void
binaryEquivalent(int num, int base) {
  if (num == 0)
    return;
  binaryEquivalent(num / base, base);
  cout << num % base;
}

...which will provide the following output upon execution:

Code:

5 (base 2) = 101
5 (base 8) = 5

Now, roll up your sleeves & study what has happened until it is clear.

Quote:

If I am to write a non-recursive function, not using bitwise operations, to print out a non-negative number in binary, how would I do it?

The guts of the problem can be found in the expression num / base where both numerator & denominator are integers.
Once you understand integer division, look at the cout statement which emits the expression num % base. Modulo arithmetic is the second aspect of the problem which needs to be understood.
In tracing execution, the recursion continues to iterate (& this word is chosen for a specific reason...) until no more non-zero division can be performed. A related problem is expressing 128 (decimal) as 1 * 10^2 + 2 * 10^1 + 8 * 10^0.

If you understand that this algorithm is simply walking through the most significant digit down to the least significant digit, change the "iteration" (there's that word again...) from recursion to iteration. You still will be doing the integer division followed by finding the remainder, but perform the same order of operations without the recursion.

Most likely, this won't be clear the first time through. It may not be clear by the third time through, but write some more examples in code, & step through execution. If you want to use a debugger, great. Otherwise, throw in lots of cout statements.

If you still have questions, feel free to post them here, but make your questions specific. The goal of anyone here is to help you find the solution yourself. Simply providing you the final answer doesn't help you refine your troubleshooting skills; providing you the answer only refines the ability to beg.

Kimmo · #3 20-Jan-2010, 00:06

Quote:

Originally Posted by program_help

how would I do it?

Turn your recursive call chain into a for loop and reverse the result.

You cannot simply cout the result this way; you have to store it somewhere.

It could look like...

CPP / C++ / C Code:

/* return value? */ intToBin_noBinaryOperators(size_t value, /* others...? */)
{
    // something goes here?

    for (; value > 0; value /= 2)
    {
        // something here
    }

    // reverse
    // do something?
    // return something?
}

CPP / C++ / C Code:

void binaryEquivalent(int num, int base)
{
  if (num == 0)return;
  {
    binaryEquivalent(num/base, base);
    cout<< num % base; 	
  } 
}

Firstly, in my opinion, there should be a 'print' somewhere in the function name. Perhaps it's just me, but when I see 'binaryEquivalent' I immediately assume I can neatly use this function to turn, say, an int to a binary representation. But I cannot. Or well, I guess you COULD if you changed cout's buffer before calling this function, but that doesn't seem like an ideal solution. A more fitting name could be 'printBitPattern'?

Second, your 'base' parameter is useless. In fact, it's even more, it's misleading! When I read that I think I'm supposed to provide an integer and the base for the integer. But alas, no, I'm supposed to provide the base for... Binary? Really... Can a binary system REALLY be in any other base than 2?

Third, since you say "unsigned integer", shouldn't your first argument reflect this somehow? Perhaps 'unsigned int' for the type would be more suitable?

Fourth, your function body is a bit misleading too. What you actually do is this:

CPP / C++ / C Code:

if (num == 0)
{
    return;
}

binaryEquivalent(num/base, base);
cout<< num % base;

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
run script command on ns2.26	newbie06	Computer Software Forum - Linux	66	16-Jan-2010 10:53
Compiling C btrieve programs in VS 2005	emanresu	C Programming Language	1	16-Nov-2009 03:19
Problem executing nam-1.13	RodolfoAlvizu	Computer Software Forum - Linux	20	28-Feb-2009 15:23
Flex and bison coding	lucky88star	C++ Forum	5	24-Dec-2007 11:57
Need Help with input files.	Efferus	C++ Forum	2	24-Nov-2007 16:19

Non-Recursive function

Re: Non-Recursive function

Re: Non-Recursive function