A good bank of solved recursion problems in C/C++/Java/C#

Question

I saw this question, but the answers there are not very relevant. A friend needs a bank of solved recursion problems to help him study for a test tomorrow.

He learned the issue theoretically, but is having problems grasping how to actually solve recursion problems. Do you know a good source of solved recursion problems (preferably in C, but can be in a C-style language as well) available on the net?

Note - examples in functional languages will not help much here. My friend is in a study race to pass his test tomorrow, and I'm sure switching languages will just confuse him at this point (it might be educational on other, less stressed times).

Answer 1

One of the best ways to learn recursion is to get some experience in a functional programming language such as Haskell or Lisp or Scheme.

So finding recursive problems can be reduced to finding some problems and answers related to functional programming languages. Here's an example 99 lisp problems.

It really only takes 5 minutes to learn Scheme or Lisp so you can get started with examples right away for the test tomorrow you mentioned.

Another great way to learn recursion is to get some practice in mathematical proofs involving induction.

---

Key concepts relating to recursion:

With recursion you don't need to know how to solve the problem. You just need to know 2 things. 1) how to solve the smallest instance of the problem, and 2) how to break it up into smaller parts.

Equivalently, you just have to keep in mind that you need: 1) a base case and 2) a recursive case.

The base case handles 1 single instance of what you want to do with smallest input.

The recursive case breaks the problem into a subproblem. Eventually this subproblem will reduce to the base case.

Example:

//1+...+n = n*n(+1)/2 = sumAll(n):

int sumAll(int x)
{
  if(x == 0) //base case
    return 0; 
  else
    return sumAll(x-1) + x; //recursive case
}

It is important to understand that the base case is not hard to figure out. It just has to exist. Here is an equivalent solution for x> 0:

//1+...+n = n*n(+1)/2 = sumAll(n):
int sumAll(int x)
{
  if(x == 1) //base case
    return 1; 
  else
    return sumAll(x-1) + x; //recursive case
}

Answer 2

This is going to sound like a very lame answer, but recursion is a paradigm that's often very hard to grasp at the first for beginners. It will take more than a day's meditation on the subject for your friend to firmly grasp the concept.

You may want to have him peruse Project Euler for a potential direction to study.

Answer 3

I think Haskell's syntax is great for thinking recursively, because the pattern matching construct makes the base case and the recursive case so obvious. Translating this into another language is then fairly straightforward.

sumAll [] = 0
sumAll (x:xs) = x + sumAll xs

To understand this, you really only need to know that

• [] represents an empty list,
• (x:xs) splits a list into a head (x) and a tail (xs)

You don't need to learn all of Haskell (which is, let's face it, hard) - but doing some of the basics certainly helps you think in recursion.

Answer 4

This article explains recursion and has some simple C examples for traversing linked list and binary tree

Answer 5

Read SICP(Structure and Interpretation of Computer Programs)

Answer 6

this is good

Answer 7

#include<iostream>
using namesspace std;
int E(int x);
int main()
{
int x;
cout<<E(x)<<endl;
return 0;
}
int E(int x)
{
return (x)?x%10+E(x/10):0;
}