I have a recursive function called fun that process a list by repeatedly subdividing and operating on halves of the list by repeatedly subdividing and operating on halves of the list.

The base case is when the function is asked to operate on a function of size 1. It requires performing the step: fun(left) + fun(right). If each function call consumes 100 bytes of memory, how many bytes will be on the activation stack when the function is at it's peak memory consumption for a list of size 8?

I would imagine it being 800 bytes since, it calls upon each size being 100 bytes. Am I interpreting this question right or no? Is the relation between size and bytes off?

# How to solve this recursion problem?

Page 1 of 1## 4 Replies - 461 Views - Last Post: 09 February 2016 - 10:50 PM

##
**Replies To:** How to solve this recursion problem?

### #2

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:28 PM

Are you asking us to answer your homework question/problem for you?

### #3

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:37 PM

No I;m asking if my answer, 800 bytes, is right. If not, what am I doing wrong?

### #4

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 04:46 PM

100 bytes per call

Each call cuts the list in half

The list size is 8

So how many times must the list be cut in half, then each half in half {repeat recursively}? That's the number of times the function is called. Times 100bytes per call.

Its not a straight 8*100bytes. You have to walk through the logical operation to see how many times the function is called.

If nothing else, just write a quick bit of code to walk through it and count the number of times the function is called.

Each call cuts the list in half

The list size is 8

So how many times must the list be cut in half, then each half in half {repeat recursively}? That's the number of times the function is called. Times 100bytes per call.

Its not a straight 8*100bytes. You have to walk through the logical operation to see how many times the function is called.

If nothing else, just write a quick bit of code to walk through it and count the number of times the function is called.

This post has been edited by **tlhIn`toq**: 09 February 2016 - 04:56 PM

### #5

## Re: How to solve this recursion problem?

Posted 09 February 2016 - 10:50 PM

Page 1 of 1