一道算法题，有什么好的思路吗？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2749 天前的主题，其中的信息可能已经有所发展或是发生改变。

写一个递归函数，输入一个数组，比如数组是['a','b','c']，那么输出

<a>
 <b>
  <c>
  </c>
 </b>
</a>

能用 ruby 写更好。

第 1 条附言 · 2017-06-02 10:13:26 +08:00

也是最近才开始有空尝试花个 1-2 小时刷刷题....算法能力较弱。好吧，就是道“题”，配不上“算法”二字行了吧....无论如何还是谢谢各位回复

Ruby

函数

算法

输入

15 条回复 • 2017-06-02 21:54:21 +08:00

bbx

2017-06-02 09:24:55 +08:00

递归

whatot

2017-06-02 09:25:30 +08:00

入栈出栈，不麻烦吧。递归的话，函数式编程的惯用手法，head:tail。

whatot

2017-06-02 09:30:01 +08:00

参考 haskell 里面的快排
https://learnxinyminutes.com/docs/haskell/

qsort [] = []
qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
where lesser = filter (< p) xs
greater = filter (>= p) xs

kindjeff

2017-06-02 09:34:47 +08:00

用栈就可以

coderluan

2017-06-02 09:36:00 +08:00

没感觉这是“算法题”，有什么特殊的吗？

linxy

2017-06-02 09:39:21 +08:00

怎么有种自己的作业自己做的感觉

wwsww

2017-06-02 09:40:57 +08:00

@coderluan need a recursive function，直接写两三行就搞定了，但明确要求用递归，一下没思路了就。。。

proudzhu

2017-06-02 09:58:27 +08:00 via iPhone

递归找最外层的 <char></char> 就行了吧

AlphaTr

2017-06-02 10:00:40 +08:00

JS 的写法：

```javascript
var html = function (list) {
var indent = lines => lines.split('\n').map(item => ' ' + item).join('\n');
return list.length > 1 ? `<${list[0]}>\n${indent(html(list.slice(1)))}\n</${list[0]}>` : `<${list[0]}>\n</${list[0]}>`
}
```

geelaw

2017-06-02 10:04:49 +08:00

要把一个非递归函数写成递归，那是很容易的，举个例子：

```C++
template <typename TIt>
std::string const theAlgo(TIt &&begin, TIt &&end)
{
std::string result;
std::string helper1{"<"},helper2{">"},helper3{"</"};
for (; begin != end; ++begin) result = helper1 + *begin + helper2 + result + helper3 + *begin + helper2;
return std::move(result);
}
```

上面是非递归，下面是递归：

```C++
template <typename TIt>
std::string const theAlgo(TIt &&begin, TIt &&end, bool shouldWork = true)
{
if (!shouldWork) return "";
theAlgo(std::forward(begin), std::forward(end), false);
std::string result;
std::string helper1{"<"},helper2{">"},helper3{"</"};
for (; begin != end; ++begin) result = helper1 + *begin + helper2 + result + helper3 + *begin + helper2;
return std::move(result);
}
```

只要制造一个没用的调用即可。

当然，题目不是这个意思，实际上我可以写（伪代码）：

```自然语言
TheAlgo(array, pos = 0)
____if (pos == array.length) return "";
____return "<" + array[pos] + ">" + TheAlgo(array, pos + 1) + "</" + array[pos] + ">";
```

就是把循环变成递归，很无聊。

seeker

2017-06-02 10:09:40 +08:00

这也叫算法题了？是不是过一段时间 hello world 也叫算法题了哦。

besto

2017-06-02 10:12:20 +08:00

C 语言带函数头尾也只需要 5 行搞定。
void fun(char **list, int index, int end) {
printf("%*s<%s>\n", index, "", list[index]);
if (index < end - 1) fun(list, index + 1, end);
printf("%*s</%s>\n", index, "", list[index]);
}

wwsww

2017-06-02 10:13:50 +08:00

@geelaw 明白思路了！谢谢啊！

loadinger

2017-06-02 16:15:20 +08:00

var arr = ['a', 'b', 'c', 'd'];
arr.reverse().reduce(function(a, b, c){
return Array(arr.length - c).join('-') + '<' + b + '>\n' + a + Array(arr.length - c).join('-') + '</' + b + '>\n';
}, '');

这样可以撒?

natat

2017-06-02 21:54:21 +08:00

chars = ['a', 'b', 'c']

def chars_print(chars, spaces):
if len(chars) > 0:
print(spaces + '<' + chars[0] + '>')
chars_print(chars[1:], spaces + ' ')
print(spaces + '</' + chars[0] + '>')

chars_print(chars, '')

python 的解法，为啥上面的代码都那么的乱，是排版的锅？