如何重写递归函数以使用循环? [英] How to rewrite a recursive function to use a loop instead?

问题描述

这个堆栈溢出线程声称每个递归函数都可以写成一个循环.

This stack overflow thread claims that every recursive function can be written as a loop.

哪些递归函数不能使用循环来重写?

这完全有道理.但是我不确定如何将以下递归函数表示为循环，因为它具有前递归逻辑和后递归逻辑.

It makes complete sense. But I'm not sure how to express the following recursive function as a loop because it has a pre recursive piece of logic and a post recursive piece of logic.

显然，解决方案无法使用goto语句.代码在这里:

Obviously the solution cannot use the goto statement. The code is here:

def gen_perms(lst, k, m):

    if k == m:
        all_perms.append(list(lst))
    else:
        for i in xrange(k, m+1):

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

            gen_perms(lst, k+1, m)

            #swap char
            tmp = lst[k]
            lst[k] = lst[i]
            lst[i] = tmp

调用它将是这样的:

all_perms = []
gen_perm([1, 2, 3], 0, 2)

并生成列表1,2,3的每个排列.

and it generates every permutation of the list 1,2,3.

推荐答案

我对python语法不太熟悉，但是假设python可以嵌套，以下代码(在'c'中)应该不太难翻译用于声明.

I am not too familiar with the python syntax, but the following code (in 'c') shouldn't be too hard to translate assuming python can do nested for statements.

int list[3]={1,2,3};
int i,j,k;

for(i=0;i < SIZE;i++)
for(j=0;j < SIZE;j++)
for(k=0;k < SIZE;k++)
if(i!=j && j!=k && i!=k)
printf("%d%d%d\n",list[i],list[j],list[k]);

这篇关于如何重写递归函数以使用循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！