一个很好的 C/C++/Java/C# 递归解决方案库

A good bank of recursion solutions in C/C++/Java/C#

提问by ripper234

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?

他从理论上了解了这个问题，但在掌握如何实际解决递归问题方面遇到了问题。您是否知道网络上已解决的递归问题（最好是 C，但也可以是 C 风格的语言）的一个很好的来源？

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).

注意 - 函数式语言的例子在这里没有多大帮助。我的朋友正在参加明天通过考试的学习竞赛，我敢肯定，此时切换语言只会让他感到困惑（这可能对其他压力较小的时间具有教育意义）。

采纳答案by qrdl

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

这篇文章解释了递归，并有一些简单的 C 例子来遍历链表和二叉树

回答by Brian R. Bondy

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.

学习递归的最好方法之一是获得一些函数式编程语言的经验，例如 Haskell、Lisp 或 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.

因此，查找递归问题可以简化为查找一些与函数式编程语言相关的问题和答案。这是99 个 lisp 问题的示例。

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.

学习 Scheme 或 Lisp 真的只需要 5 分钟，这样您就可以立即开始使用示例来进行您提到的明天的测试。

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.

使用递归，您无需知道如何解决问题。你只需要知道两件事。1) 如何解决问题的最小实例，以及 2) 如何将其分解为更小的部分。

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

同样，您只需要记住您需要：1) 基本情况和 2) 递归情况。

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

基本案例处理您想要用最小输入执行的操作的 1 个单个实例。

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:

重要的是要了解基本情况并不难计算。它必须存在。这是 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
}

回答by Boydski

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 Eulerfor a potential direction to study.

您可能想让他仔细阅读欧拉计划，寻找潜在的研究方向。

回答by slim

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.

我认为 Haskell 的语法非常适合递归思考，因为模式匹配构造使基本情况和递归情况如此明显。将其翻译成另一种语言是相当简单的。

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)

• [] 代表一个空列表，
• (x:xs) 将列表拆分为头部 (x) 和尾部 (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.

你不需要学习所有的 Haskell（也就是说，让我们面对现实吧，很难） - 但是做一些基础知识肯定会帮助你思考递归。

回答by Vinay

Read SICP(Structure and Interpretation of Computer Programs)

阅读SICP（计算机程序的结构与解释）

回答by ali

#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;
}

回答by Manas maity

In c /c++ language a function can call itself and this case is called Recursion. Mainly recursion have two cases:

在 c / c++ 语言中，函数可以调用自身，这种情况称为递归。递归主要有两种情况：

1. Base case.
2. recursive case.

1. 基本情况。
2. 递归案例。

and we have some recursive categories like as...

我们有一些递归类别，例如...

1. Liner recursion
2. Binary recursion
3. Nested recursion
4. Mutual recursion
5. Tail recursion

1. 线性递归
2. 二进制递归
3. 嵌套递归
4. 相互递归
5. 尾递归

Here take a example to discuss recursion ...

这里举个例子来讨论递归......

// a recursive program to calculate NcR  //
#include <stdio.h> 
int ncr(int x,int y)
{
    if(y>x)
    {
        printf("!sorry,the operation can't processed.");
        getch();
        exit(1);
    }
    else if(y==0 ||y==x)   //base case
    {
        return(1);
    }
    else
    {
        return(ncr(x-1,y-1)+ncr(x-1,y));  //recursive case
    }
}