Reputation: 15

Number Pattern Function in c++ using recursion

Implement the following function using recursion. Do not use any local variables or loops.

void pattern(unsigned int n)

// Precondition: n > 0;

// Postcondition: The output consists of lines of integers. The first line

// is the number n. The next line is the number 2n. The next line is

// the number 4n, and so on until you reach a number that is larger than

// 4242. This list of numbers is then repeated backward until you get back

// to n.

/* Example output with n = 840:

840

1680

3360

6720

3360

1680

840 */

//This is my code

#include <iostream>

using namespace std;

void pattern(unsigned int n)
{
    if(n > 0)
    {
        cout << n << endl;
        return pattern(n * 2);
    }else if( n > 4242)
    {
        return pattern(n / 2);
    }
}

int main()
{
    pattern(840);
    return 0;
}

//My code just keeps doubling n, it doesn't divided back to the original n.

Upvotes: 1

Answers (5)

Oliver Dain

Reputation: 9953

The other two answers point out one of the issues (that n > 0 is true whenever n > 4242 is true), but the other issue is that you only call pattern with a n / 2 if n > 4242. So you'll end up "ping-ponging" back and forth. For example, in the example output you showed in your question, when you hit 6720 you'd halve that to call pattern(3360), but on the next call you'd then call pattern with 3360 doubled since 3360 < 4242.

I think the most obvious way to do this is to split this into two functions and add a "direction" boolean indicating if you're going up or down:

void pattern(unsigned int n) {
   pattern_with_dir(n, true);
}

void patten_with_dir(unsigned int n, bool increase) {
    if (n <= 0) {
        return;
    }
    cout << n << endl;
    if (n > 4242) {
        pattern_with_dir(n, false);
    } else {
        if (increase) {
            pattern_with_dir(n * 2, true);
        } else {
            pattern_with_dir(n / 2, false);
        }
    }
}

Note you could also split this into 3 functions:

void pattern(unsigned int n) {
   pattern_up(n);
}

void pattern_up(unsigned int n) {
    cout << n << endl;
    if (n > 4242) {
        pattern_down(n);
    } else {
       pattern_up(n * 2);
    }
}

void pattern_down(unsigned int n) {
    if (n <= 0) {
        return;
    }
    cout << n << endl;
    pattern_down(n / 2);
}

But the most concise solution is to make use of the recursion stack to help you count back down:

void pattern(unsigned int n) {
   // Going up
   count << n << endl;
   if (n <= 4242) {
       pattern(n*2);
   }
   // this will be called "on the way back down"
   count << n << endl;
}

Upvotes: 1

Nandu

Reputation: 808

// ConsoleApplication3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <iostream>

using namespace std;

void pattern(unsigned int n)
{
    cout << n << endl;
    if (n > 4242) {
        cout << n << endl;
        return ;
    }

        pattern(n * 2);

    cout << n << endl;

    return ;
}

int _tmain(int argc, _TCHAR* argv[])
{
    pattern(840);
    return 0;
}

Upvotes: 0

Rik

Reputation: 3887

It will never hit the else if, because then the first criteria (>0) is still true and it will end up in the first if statement.

Make the first criteria

if(n > 0 && n <= 4242) {
...
} else if(n > 4242){
...
}

Or invert the if and else if

if(n > 4242) {
    return pattern(n/2);
} else if (n >0) {
    return pattern(n*2);
}

Upvotes: 0

Andrey Nasonov

Reputation: 2629

void pattern(unsigned int n)
{
    if (n > 0)
    {
        cout << n << endl;
        if (n < 4242)
            pattern(n * 2);
        cout << n << endl;
    }
}

Upvotes: 0

Neil Kirk

Reputation: 21773

if( n > 4242) will only be evaluated if (n > 0) is not true. But whenever n > 4242 is true, so will n > 0 be.

Upvotes: 0

Number Pattern Function in c++ using recursion

Answers (5)

Related Questions