CODEWITHSUNDEEP
javaalgorithmrecursiongeometry
Dillon Burton
Dillon Burton

Reputation: 363

Creating a recursive algorithm

I have been looking at the current problem on Coding Bat:

"We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows."

I understand what the problem is asking for, and I understand how recursion works. For example, if I am given a recursion function I can work it out by hand and show what the output will be.

The problem is actually creating the recursion function from a given problem, such as this one. I'm not sure how to actually set this up and do it recursively. Are there some sort of rules to follow when actually setting up a recursion problem? I can only find examples that show you how recursion works, not showing you how to actually solve a recursion problem. Any help understanding how to get ready to write the actually recursion algorithm would be appreciated.

Upvotes: 1

Views: 358

Answers (4)

Arpit
Arpit

Reputation: 12797

Try this code:

#include <iostream>
using namespace std;
int sumf(int row,int sum){
if(row==0)     //basecase which ends the recursion.
return sum;
else
{sum=row+sum;
return sumf(--row,sum);   // repeating the process.
}}
int main() {
    cout<<"sum is: "<<sumf(5,0)<<endl;
system("pause");
    return 0;
    }

This is the video which make you understand about recursion.(forget about language just focus on concept.)

http://www.youtube.com/watch?v=sNJQrtGD1Nc

Upvotes: 0

Javadrien
Javadrien

Reputation: 201

if(rows == 1) return 1; is useless here.

For the recursion global issue, you must disassemble your problem and find:

  1. An exit rule (can be an initial value like in your example, or some exit condition on one of the inputs)
  2. A stepping process (what do you have to do with the previous input to get the next one)

And assemble them in a function that calls itself.

Upvotes: 2

Fallup
Fallup

Reputation: 2427

Roughly:

  1. Always look at the problem and try to find out if it can be divided into subproblems of the same type. That's a first hint that you can possibly use a recursion. Essentially you are looking for a smaller instances/versions of an actual problem.

    Recursion takes therefore a top down approach(from the more complex to simpler problem cases).

  2. When you can find such cases then you should find out what is the relation between the "bigger" case and the "smaller" case and you have your recursion step.

  3. The final thing is to find out the terminating condition or what is the smallest or last case where you want to stop.

You probably know about this but if not it might help you.

Upvotes: 4

sr01853
sr01853

Reputation: 6121

For a recursion algorithm,

first design the base case, for which the function should start the unwinding of the stack or to return the base value.

Then design the algorithm to be actually done, for each of the non-base cases

Upvotes: 2

Related Questions