CODEWITHSUNDEEP
c++recursionusing
PhpLover1337
PhpLover1337

Reputation: 45

combinatorial function c++ using Recursion

Now this is the combinatorial function if you don't know it:

C(n,k)= { 1 if k=0 or k = n C(n−1,k−1)+C(n−1,k) otherwise

Now, What I really need is to use recursion to print a Pascal's triangle.

Ok,so what I've done so far is this simple recursion function:

#include   <iostream>
using namespace std;

int Pas(int r, int c) {
    if (c == 0 || c == r) {
        return 1;
    } else {
        return Pas(r - 1, c - 1) + Pas(r - 1, c);
    }
}

int main(){

    cout << Pas(4,2) << endl;

    return 0;
}

Now this function computes perfectly for example:

Pas(4,2) = 6

But I'm having problem using it to print the whole Pascal's triangle, because I'm new into C++ and especially recursion ..

I'd appreciate any feedback, and I hope that someone would help figure out this problem. But I'd appreciate it more if you guys don't just give me the whole answer (code) just like that; I want to learn.

Thanks!

Upvotes: 2

Views: 1145

Answers (3)

pingul
pingul

Reputation: 3473

Something similar to this might to the job

void printTriangle(int printRows, int a = 1, int b = 0)
{
    if (a > printRows) return;
    int val = Pas(a, b);
    cout << val << " ";
    if (a == b) {
        cout << endl;
        printTriangle(printRows, a + 1, 0);
    } else {
        printTriangle(printRows, a, b + 1);
    }
}

Running printTriangle(7) should print the first 7 rows.

Upvotes: 1

Christophe
Christophe

Reputation: 73376

If you are allowed to use your recursive function in a loop, the easiest way would be something like: 

int n=4; 

for (int i=0; i<=n; i++) {
    for (int j=0; j<=i; j++) {
        cout << Pas(i,j)<<" "; 
    }
    cout <<endl; 
}

If you want to reinforce the layout, you coud also #include <iomanip> and <limits> to use a fixed size number output, using the number of digits required to display an integer: just replace the output statement with: 

    cout << setw(numeric_limits<int>::digits10+1)<<Pas(i,j);

Edit:

You could easily build a recursive function to print lines of the triangle: 

void PrintPas(int r) {
    if (r==1) 
       cout << Pas(1,0); 
    else {
        PrintPas(r-1);
        for (int c=0; c<=r; c++)
           cout << Pas(r,c)<< " ";
    }
    cout <<endl; 
}

Edit 2

If you want a fully recursive version: 

void PrintPas(int r, int c) {
    if (r==1) 
       cout << Pas(1,0)<<"  "; 
    else if (c==-1) {
        PrintPas(r-1,r-1);
    }
    else {
        PrintPas(r,c-1); 
        cout << Pas(r,c)<< " ";
    }
    if (r==c)
       cout <<endl; 
}

Online demo

Upvotes: 1

Dafang Cao
Dafang Cao

Reputation: 907

Tail recursion is the recursive equivalent to iterative loops. The following function when called with sum(0, 5)

int sum(int start, int end, int resultSoFar = 0) {
    if (start == end) return resultSoFar;
    return sum(start + 1, end, resultSoFar + start);
}

is equivalent to the iterative function called with sum(0, 5).

int sum(int start, int end) {
    int resultSoFar = 0;
    for (int i = start; i < end; i++) {
        resultSoFar += i;
    }
    return resultSoFar;
}

Upvotes: 1

Related Questions