化递归为迭代 求助

来源：百度知道 编辑：UC知道 时间：2024/05/18 04:59:29
设f（a）*f（b）=f（a+b），
因此设k是整数，f（2k+1）=f（k）*f（k）*f(1),
f(2k)=f(k)*f（k）。
这样在f(1)已知的条件下可以用递归的方法求出任意f（n）。

现在要求用这种思想（奇数则减一除以二，偶数直接除以二）的迭代手法表示，何解？

谢谢
这位大哥说的似乎是递归

是说对于任意的n
当n为偶数时，先求 f(n/2)
当n为奇数时，先求 f(n-1/2)
再对f(n/2)或f(n-1/2)重复上述过程，直到f(n/2)或f(n-1/2)已知或能求出结果。然后
迭代，求出f(n)

例 n=4
先求f(4/2)=f(2)
对f(2),
先求f(2/2)=f(1),由于f(1)已知，
所以可以求出f(2)=f(1)*f(1)=f(1)^2,
从而f(4)=f(2)*f(2)=f(1)^4

例 n=5
先求f((5-1)/2)=f(2)
对f(2),
先求f(2/2)=f(1),由于f(1)已知，
所以可以求出f(2)=f(1)*f(1)=f(1)^2,
从而f(5)=f(2)*f(2)*f(1)=f(1)^5

一种方法是从中推导出公式。这很简单，我想你要的不是这样的答案。你是在修炼算法。
我想到的是用堆栈来做。
java版的
package test;

import java.util.Stack;

public class MathQuestion {
private static final int VALUE_FOR_ONE = 2;

/**
* i要求大于0
*/
public static final int f(int i) {
if (i == 1)
return VALUE_FOR_ONE;
int result = 1;
Stack stack = new Stack();
stack.push(new Integer(i));
while (!stack.empty()) {
int num = ((Integer) stack.pop()).intValue();
if (num == 1) {
resu