1

我试图理解函数递归，但我被困在我拥有的一个片段上。我完全理解你一遍又一遍地调用直到数字匹配 1 的阶乘示例，但这里的问题是，首先执行什么？foreach 循环还是递归调用？

这是片段：

例如，给定初始字符串 'abc' ，这将是调用 foreach 循环时第一次执行的值（ permute($str) as $permutation ）？

function permute($str)
{
    if (strlen($str) < 2) 
    {
        return array($str);
    }

    $permutations = array();

    $tail = substr($str, 1);

    foreach (permute($tail) as $permutation) 
    {
        $length = strlen($permutation);

        for ($i = 0; $i <= $length; $i++) 
        {
           $permutations[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }

    /* Return the result */
    return $permutations;
}
4

2 回答 2

0

寻找一些关于如何正确进行递归的技巧。这个想法是逐步将问题减少到微不足道的情况。不要试图可视化整个调用层次结构。

你似乎不知道如何解决这个问题。实现递归算法的最简单方法通常是使用两个函数：一个递归函数和一个调用它一次以开始滚动的助手。看看这个：

function permute($string) {
    $permutations = array();
    permuteHelper('', $string, $permutations);
    return $permutations;
}

function permuteHelper($prefix, $string, array &$store) {
    $length = strlen($string);
    if($length === 0) {
        $store[] = $prefix;
    }
    else {
        for($i = 0; $i < $length; $i++) {
            permuteHelper($prefix . $string[$i], substr($string, 0, $i) . substr($string, $i + 1), $store);
        }
    }
}

学分：改编自Java 中的这个实现。

于 2013-09-17T14:24:48.560 回答
0

你有一段无意义的代码。

该函数permute始终返回一个空数组，因为$permutations该函数返回的值自初始化以来从未更改过（从初始array()值开始）。

该函数以交互方式调用自身，将字符串的尾部递减，直到尾部仅包含 2 个字符。然后它以正常和相反的顺序回显这些字符。就这些

所以运行permute('abc')你只会看到bccb并收到array()函数结果。

我的变体（也适用于数组或字符串输入）

function permute($arg) {
    $array = is_string($arg) ? str_split($arg) : $arg;
    if(1 === count($array))
        return array(array_shift($array));
    $result = array();
    foreach($array as $key => $item)
        foreach(permute(array_diff_key($array, array($key => $item))) as $p)
            $result[] = $item . $p;
    return $result;
}
于 2013-09-17T14:06:41.600 回答