LoginLogin

Recursive Function

Root / Programming Questions / [.]

MZ952Created:
MZ952#1
So I recently saw an example of a recursive Function, and now I'm trying to understand it. I've written this: 
DEF SUM(A[])
 IF(LEN(A))THEN RETURN(SUM(A)+POP(A))
END
The function returns a Type mismatch error, and I'm not quite understanding why. My current reasoning is that the function is (somehow) returning an array which I inevitably am trying to assign to a variable, but I don't see why that is. This is how the function appears in my head: 
DEF SUM(A[])
 IF(LEN(A))THEN RETURN(POP(A)+POP(A)+POP(A). . .+POP(A))
END
The function calls iterations of itself LEN(A) times and sequentially sums up each iteration with the previous, returning the end result. Why is this a type mismatch?
12Me21#2
Well, for one thing, if LEN(A) is 0, you're not returning anything.
MZ952#3
Well, for one thing, if LEN(A) is 0, you're not returning anything.
Lol that fixed it entirely. It looks like on the last step of the function it attempted to return something untyped or null and the whole thing broke down from there. Can't believe that escaped me. I thought the logic was flawed somewhere. Thank you! Corrected function: 
DEF SUM(A[])
 IF(LEN(A)>.)THEN RETURN(SUM(A)+POP(A))
 COPY(A),(1)(A),.RETURN(A[.])
END
Yolkai#4
gratuitous implied zeroes...
MZ952#5
gratuitous implied zeroes...
I like the look of them. Purely cosmetic. http://smilebasicsource.com/page?pid=1052
12Me21#6
         [funmodule][04:16]g: Lumage "NEXT(.)"
                              Next breast
Simeon#7
Ok, so actually what's happening is you don't have a base case, the array will get smaller and smaller, but you have no way of returning the final result so you just don't return anything which gives an error. So this code will work 
DEF SUM(A[])
 IF LEN(A)==1 THEN RETURN A[0]
 RETURN SUM(A)+POP(A)
END
The issue with this is this does not allow empty arrays (you could simply add another base case check) A different approach: 
DEF SUM(A[])
 IF LEN(A) THEN RETURN SUM(A)+POP(A)
 RETURN 0
END
This does allow empty arrays, and is allot lot harder to prove and understand. That's because the base case is actually the second to last step (not the last): First step [1,2,3] Second step [1,2]+3 Third step [1]+5 Fourth step []+6 *FIFTH STEP* 0+6 Function returns 6. You need to convert every component into number format, that means converting an empty array to 0. Something that doesn't work is switching the return order 
'FROM'
 RETURN SUM(A)+POP(A)
'TO'
 RETURN POP(A)+SUM(A)
And this proves that SmileBASIC evaluates expressions from the right to the left. I took a class last semester called Design and Analysis of Algorithms, and that class evaluates recursive functions by pulling out their inner loops until the pattern is visible, to calculate the exact complexity in big O notation.
Simeon#8
Hey, if you haven't seen this already then you should, it's a pretty cool example of recursion 
DRAW 200,120,119

DEF DRAW X,Y,R
 IF R<2 THEN RETURN
 GCIRCLE X,Y,R
 R=R/2
 DRAW X+R,Y,R
 DRAW X-R,Y,R
END
amihart#9
My favorite example of recursion is this: 
DEF EMOD(B,P,M)
  IF P == 0 THEN RETURN 1
  IF P MOD 2 == 0 THEN
    VAR R = EMOD(B, P/2, M)
    RETURN (R*R) MOD M
  ENDIF
  RETURN ((B MOD M) * EMOD(B, P-1, M)) MOD M
END
It's for calculating exponents in modular arithmetic of the form B^P MOD M. It's useful because the size of the number you're dealing with never exceeds the sides of M. So if you're dealing with something like 4546464^6346356 mod 12, you can't evaluate "4546464^6346356" because it's too big. But you can still evaluate this problem simply by breaking it up into chunks using recursion, and the size you need at each step never exceeds 12.