recursive functions

[timmy]

may i plz get some new good problems on recursive functions?

[LB]

1. Without using stacks, write the functions for the following tree class:

template<typename T>
class Tree
{
  T data;
  Tree<T>* LBranch;
  Tree<T>* RBranch;
public:
  Tree() : LBranch(NULL), RBranch(NULL) {}
  void FillToDepth(const T& FillWith, const unsigned long& Depth)
  {
    //write code here that creates a tree to the specified depth
  }
  ~Tree()
  {
    //write code here to properly clean up all memory you allocated
  }
};

Instantiating a Tree<int> object and calling FillToDepth(5, 5) should have 63 total branches, including itself.

[Mathhead200]

Implement an array/vector search, both linear and binary.

template <typename T>
T find(vector<T> arr, T trg, int index = 0) {
   //...
}

template <typename T>
T binSearch(vector<T> arr, T trg, int start, int end) {
   //...
}

tamplate <typename T>
T binSearch(vector<T> arr, T trg) {
   return binSearch(arr, trg, 0, arr.size());
}

[m4ster r0shi]

First, write a sum function:

// sum(n) = 1 + 2 + ... + n

unsigned sum(unsigned n)
{
    if ( /*...*/ ) //...

    else return //...
} 

Then, write a fibonacci function:

// fib(0) = 0
// fib(1) = 1
// fib(n) = fib(n - 1) + fib(n - 2)

unsigned fib(unsigned n)
{
         if ( /*...*/ ) //...
    else if ( /*...*/ ) //...

    else return //...
}

Finally, modify your fibonacci function to
take advantage of the tail call optimization.

Useful links:

http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_01.aspx
http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_02.aspx
http://www.codeproject.com/KB/cpp/Recursion_Prmr_CPP_03.aspx

[kev82]

Solve the four fours problem.

Given an integer, n, you must calculate if it is possible to produce this integer using only +-*/() and the number 4. You must use exactly 4 fours.

eg

1: (4+4)/(4+4)
2: (4*4)/(4+4)

[Mathhead200]

Here's one I did a while back. Define integer addition and subtraction operations using only bitwise and comparison operators. (And of course using recursion.)

//using only = & | ^ ~ << >> == != and no for/while/goto loops
int add(int a, int b);
int subtract(int a, int b);
//(I think that's all of them...) 

[kev82]

@Mathhead200

Can you really do it with those function signatures. Don't you also need to pass the carry around?

Ignore that, was being daft. Solved it now.

[m4ster r0shi]

How did you do it? I used ==, ^, & and <<, only once each, for addition and ~ only once for subtraction.

[moorecm]

Quicksort is a good example for recursion. So is any kind of hierarchical parsing (XML, for example).

[kev82]

Probably the same way as you as I also used the same symbols in the exact order you've written them.

[Mathhead200]

m4ster r0shi, I didn't mean you need to use all of them. But that was for him to figure out.

[Mathhead200]

moorecm wrote:

[A good example of recursion] is any kind of hierarchical parsing (XML, for example).

Oo. My first true need for recursion was when I made a Perl script that recursively iterated your directory structure (from some root directory) and outputted to an XML file with the information. It was sweet! (Also the XML was well formatted. I used a global variable for the leading white space.)